Connectivity vs. reachability

DOI10.1016/0890-5401(91)90065-AMaRDI QIDQ757048zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Howard Karloff, Tomasz Radzik

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(91)90065-a

zbMATH Keywords

reachabilityconnectivityqueriesoracle

Mathematics Subject Classification ID

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

Recommendations

• Reachability Problems: An Update
• Reachability is harder for directed than for undirected finite graphs
• Testing st-Connectivity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

Cites work

• A generalized model for understanding evasiveness
• On the Complexity of Timetable and Multicommodity Flow Problems

Cited in

(4)

• scientific article; zbMATH DE number 2090011 (Why is no real title available?)
• Reachability Problems: An Update
• Reachability in choice networks
• The complexity of graph connectivity

This page was built for publication: Connectivity vs. reachability

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