Reachability Problems: An Update

DOI10.1007/978-3-540-73001-9_3MaRDI QIDQ5426862zbMATH OpenOpenAlexFDO

Authors Eric Allender

Publication date 13 November 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73001-9_3

zbMATH Keywords

survey

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Recommendations

• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Planar and grid graph reachability problems
• Connectivity vs. reachability
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• Space complexity of the directed reachability problem over surface-embedded graphs

Cited in

(11)

• Reachability Problems on Directed Graphs
• Planar and grid graph reachability problems
• When Is Reachability Intrinsically Decidable?
• Space complexity of the directed reachability problem over surface-embedded graphs
• A repeated-update problem in the DeltaBlue algorithm
• scientific article; zbMATH DE number 2144766 (Why is no real title available?)
• Space Complexity of Reachability Testing in Labelled Graphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Balancing bounded treewidth circuits
• Space complexity of reachability testing in labelled graphs
• Complexity of testing reachability in matroids

This page was built for publication: Reachability Problems: An Update

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