Undirected ST-connectivity in log-space

DOI10.1145/1060590.1060647MaRDI QIDQ3581436zbMATH OpenOpenAlexWikidataFDO

Authors Omer Reingold

Publication date 16 August 2010

Published in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1060590.1060647

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Undirected connectivity in log-space
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• scientific article; zbMATH DE number 1256637
• Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• A fast randomized LOGSPACE algorithm for graph connectivity
• A fast randomized LOGSPACE algorithm for graph connectivity
• Connectivity in Lattice-Ordered Spaces
• Time--Space Lower Bounds for Directed st-Connectivity on Graph Automata Models

Cited in

(70)

• Universal algebra and hardness results for constraint satisfaction problems
• Affine systems of equations and counting infinitary logic
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
• \(\text{RL}\subseteq \text{SC}\)
• Balancing bounded treewidth circuits
• The complexity of problems for quantified constraints
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Weighted group search on a line \& implications to the priority evacuation problem
• Random walks on graphs and Monte Carlo methods
• Combinatorial algorithms for distributed graph coloring
• On the complexity of matrix rank and rigidity
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Graph decomposition for memoryless periodic exploration
• Simple agents learn to find their way: an introduction on mapping polygons
• Poisson approximation for non-backtracking random walks
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• On the CSP Dichotomy Conjecture
• Bravely, moderately: a common theme in four recent works
• Basic Facts about Expander Graphs
• Combinatorial algorithms for distributed graph coloring
• STCON in directed unique-path graphs
• Graph Decomposition for Improving Memoryless Periodic Exploration
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• s-t connectivity on digraphs with a known stationary distribution
• An improved strategy for exploring a grid polygon
• The complexity of intersecting finite automata having few final states
• A Logspace Algorithm for Partial 2-Tree Canonization
• Expander graphs and their applications
• Directed st-Connectivity Is Not Expressible in Symmetric Datalog
• On Linear Secret Sharing for Connectivity in Directed Graphs
• Pure Pointer Programs with Iteration
• Finding Reductions Automatically
• The Simple Reachability Problem in Switch Graphs
• Undirected connectivity in log-space
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• Introducing Quasirandomness to Computer Science
• The parallel complexity of graph canonization under abelian group action
• Problems complete for deterministic logarithmic space
• Memoryless routing in convex subdivisions: random walks are optimal
• More efficient periodic traversal in anonymous undirected graphs
• scientific article; zbMATH DE number 1559538 (Why is no real title available?)
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Energy consumption of group search on a line
• The diameter of randomly perturbed digraphs and some applications
• Memory Efficient Anonymous Graph Exploration
• Correctness of linear logic proof structures is NL-complete
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
• Absorbing random walks and the NAE2SAT problem
• Cyclic extensions of order varieties
• Quantum computing, postselection, and probabilistic polynomial-time
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• On expander graphs and connectivity in small space
• Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
• Uniform Constraint Satisfaction Problems and Database Theory
• Faster walks in graphs: a O(n^2) time-space trade-off for undirected s-t connectivity
• Algorithms for \(p\)-Faulty Search on a half-line
• Derandomizing random walks in undirected graphs using locally fair exploration strategies
• On the Cook-Mertz tree evaluation procedure
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• Planar and grid graph reachability problems
• The equivalence of theories that characterize ALogTime
• The complexity of constraint satisfaction games and QCSP
• The complexity of pure literal elimination
• Distributed chasing of network intruders
• Fast periodic graph exploration with constant memory
• Setting port numbers for fast graph exploration

This page was built for publication: Undirected ST-connectivity in log-space

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