The complexity of graph connectivity

DOI10.1007/3-540-55808-X_10MaRDI QIDQ5096823zbMATH OpenOpenAlexFDO

Authors A. Wigderson

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

Mathematics Subject Classification ID

Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• A taxonomy of problems with fast parallel algorithms
• A topological approach to evasiveness
• An application of games to the completeness problem for formalized theories
• Connectivity vs. reachability
• First-order definability on finite structures
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 4106276 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• Monadic generalized spectra
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Nondeterministic Space is Closed under Complementation
• Parity, circuits, and the polynomial-time hierarchy
• Reachability is harder for directed than for undirected finite graphs
• Relationships between nondeterministic and deterministic tape complexities
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Two Applications of Inductive Counting for Complementation Problems
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
• Universal classes of hash functions

Cited in

(17)

• The complexity of planarity testing
• The g-component connectivity of graphs
• Graph connectivities, network coding, and expander graphs
• On computing the connectivities of graphs and digraphs
• scientific article; zbMATH DE number 3910097 (Why is no real title available?)
• scientific article; zbMATH DE number 4125433 (Why is no real title available?)
• Formulas versus Circuits for Small Distance Connectivity
• The parameterized space complexity of model-checking bounded variable first-order logic
• \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
• Space-efficient algorithms for reachability in directed geometric graphs
• Traversability, reconfiguration, and reachability in the gadget framework
• The complexity of growing a graph
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• The complexity of iterated reversible computation
• Superpolynomial lower bounds against low-depth algebraic circuits
• Reachability games and friends: a journey through the Lens of memory and complexity (invited talk)
• Connection between conjunctive capacity and structural properties of graphs

This page was built for publication: The complexity of graph connectivity

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