Connectivity vs. reachability

DOI10.1016/0890-5401(91)90065-AzbMATH Open0723.68046OpenAlexW2055842100MaRDI QIDQ757048FDOQ757048

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

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

zbMATH Keywords

reachabilityconnectivityqueriesoracle

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• 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)