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

dynamic graph algorithmsdominator treedecremental algorithmsstrong connectivity under failures

Mathematics Subject Classification ID

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

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

(5)

• Strong connectivity in directed graphs under failures, with applications
• Decremental maintenance of strongly connected components
• Incremental low-high orders of directed graphs and applications
• Strong connectivity in directed graphs under failures, with applications
• Dynamic Dominators and Low-High Orders in DAGs

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)