Decremental data structures for connectivity and dominators in directed graphs

DOI10.4230/LIPICS.ICALP.2017.42zbMATH Open1441.68184arXiv1704.08235MaRDI QIDQ5111373FDOQ5111373

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

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

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)

Cited In (5)

• Strong connectivity in directed graphs under failures, with applications
• 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
• Decremental maintenance of strongly connected components

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)