An efficient strongly connected components algorithm in the fault tolerant model

DOI10.4230/LIPICS.ICALP.2017.72MaRDI QIDQ5111403zbMATH OpenFDO

Authors Surender Baswana, Keerti Choudhary, Liam Roditty

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2017.72

zbMATH Keywords

directed graphfault tolerancestrongly connected components

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• An efficient strongly connected components algorithm in the fault tolerant model
• Decremental maintenance of strongly connected components
• Decremental strongly connected components and single-source reachability in near-linear time
• Strong connectivity in directed graphs under failures, with applications
• Strong connectivity in directed graphs under failures, with applications

Cited in

(5)

• Computing strongly connected components in the streaming model
• Strong connectivity in directed graphs under failures, with applications
• An efficient strongly connected components algorithm in the fault tolerant model
• Improved distributed algorithms for SCC decomposition
• 2-fault-tolerant strong connectivity oracles

This page was built for publication: An efficient strongly connected components algorithm in the fault tolerant model

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