The complexity of graph connectivity
From MaRDI portal
Publication:5096823
DOI10.1007/3-540-55808-X_10zbMath1493.68163OpenAlexW1566033350MaRDI QIDQ5096823
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55808-x_10
Related Items
The complexity of planarity testing ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Unnamed Item ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Traversability, reconfiguration, and reachability in the gadget framework ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connectivity vs. reachability
- A topological approach to evasiveness
- Universal classes of hash functions
- First-order definability on finite structures
- Relationships between nondeterministic and deterministic tape complexities
- An application of games to the completeness problem for formalized theories
- Parity, circuits, and the polynomial-time hierarchy
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Reachability is harder for directed than for undirected finite graphs
- A taxonomy of problems with fast parallel algorithms
- Nondeterministic Space is Closed under Complementation
- Two Applications of Inductive Counting for Complementation Problems
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
- Monadic generalized spectra
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
This page was built for publication: The complexity of graph connectivity
