Decremental data structures for connectivity and dominators in directed graphs

DOI10.4230/LIPICS.ICALP.2017.42MaRDI QIDQ5111373zbMATH OpenFDO

Authors Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano, Sebastian Krinninger, Nikos Parotsidis

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1704.08235

zbMATH Keywords

decremental algorithmsdominator treedynamic graph algorithmsstrong connectivity under failures

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Decremental maintenance of strongly connected components
• Strong connectivity in directed graphs under failures, with applications
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Decremental strongly connected components and single-source reachability in near-linear time
• Strong connectivity in directed graphs under failures, with applications

Cited in

(7)

• Strong connectivity in directed graphs under failures, with applications
• Incremental low-high orders of directed graphs and applications
• Dynamic Dominators and Low-High Orders in DAGs
• Strong connectivity in directed graphs under failures, with applications
• Decremental maintenance of strongly connected components
• On maximal k-edge-connected subgraphs of undirected graphs
• Faster dynamic 2-edge connectivity in directed graphs

This page was built for publication: Decremental data structures for connectivity and dominators in directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111373)