English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 anoptimum-height elimination forest. The data structure achieves worst-caseupdate time $2^{{\cal O}(d^2)}$, which matches the best known parameterdependency in the running time of a static fpt algorithm for computing thetreedepth of a graph. This improves a result of Dvo\v{r}\'ak et al. [ESA 2014],who for the same problem achieved update time $f(d)$ for some non-elementary(i.e. tower-exponential) function $f$. As a by-product, we improve known upperbounds on the sizes of minimal obstructions for having treedepth $d$ fromdoubly-exponential in $d$ to $d^{{\cal O}(d)}$.  As applications, we design new fully dynamic parameterized data structuresfor detecting long paths and cycles in general graphs. More precisely, for afixed parameter $k$ and a dynamic graph $G$, modified over time by edgeinsertions and deletions, our data structures maintain answers to the followingqueries:  - Does $G$ contain a simple path on $k$ vertices?  - Does $G$ contain a simple cycle on at least $k$ vertices?  In the first case, the data structure achieves amortized update time$2^{{\cal O}(k^2)}$. In the second case, the amortized update time is $2^{{\calO}(k^4)} + {\cal O}(k \log n)$. In both cases we assume access to a dictionaryon the edges of $G$.

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