Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

Jiehua Chen, Wojciech Czerwiński, Yann Disser +8

We present a data structure that in a dynamic graph of treedepth at most $d$, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…