Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10440282" target="_blank" >RIV/00216208:11320/21:10440282 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1137/1.9781611976465.50" target="_blank" >https://doi.org/10.1137/1.9781611976465.50</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611976465.50" target="_blank" >10.1137/1.9781611976465.50</a>
Alternative languages
Result language
angličtina
Original language name
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Original language description
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 forest. The data structure achieves worst-case update time 2^O(d^2), which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák 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 upper bounds on the sizes of minimal obstructions for having treedepth d from doubly-exponential in d to d^O(d).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GJ17-10090Y" target="_blank" >GJ17-10090Y: Network Optimization</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-1-61197-646-5
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
796-809
Publisher name
Association for Computing Machinery
Place of publication
Neuveden
Event location
Online
Event date
Jan 10, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—