Undirected ST-connectivity in log-space
From MaRDI portal
Publication:3581436
DOI10.1145/1060590.1060647zbMath1192.68374OpenAlexW2166162093WikidataQ56474406 ScholiaQ56474406MaRDI QIDQ3581436
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)
Related Items (56)
The equivalence of theories that characterize ALogTime ⋮ The complexity of constraint satisfaction games and QCSP ⋮ The diameter of randomly perturbed digraphs and some applications ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Graph Decomposition for Improving Memoryless Periodic Exploration ⋮ The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ The complexity of pure literal elimination ⋮ The complexity of intersecting finite automata having few final states ⋮ Poisson approximation for non-backtracking random walks ⋮ The parallel complexity of graph canonization under abelian group action ⋮ Balancing bounded treewidth circuits ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Memoryless routing in convex subdivisions: random walks are optimal ⋮ Algorithms for \(p\)-Faulty Search on a half-line ⋮ Graph decomposition for memoryless periodic exploration ⋮ Expander graphs and their applications ⋮ More efficient periodic traversal in anonymous undirected graphs ⋮ The complexity of problems for quantified constraints ⋮ The isomorphism problem for planar 3-connected graphs is in unambiguous logspace ⋮ Simple agents learn to find their way: an introduction on mapping polygons ⋮ On Linear Secret Sharing for Connectivity in Directed Graphs ⋮ Pure Pointer Programs with Iteration ⋮ Faster Treasure Hunt and Better Strongly Universal Exploration Sequences ⋮ Distributed chasing of network intruders ⋮ Fast periodic graph exploration with constant memory ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Absorbing random walks and the NAE2SAT problem ⋮ Setting port numbers for fast graph exploration ⋮ Random walks on graphs and Monte Carlo methods ⋮ On the CSP Dichotomy Conjecture ⋮ Combinatorial algorithms for distributed graph coloring ⋮ Cyclic Extensions of Order Varieties ⋮ Correctness of linear logic proof structures is NL-complete ⋮ Finding Reductions Automatically ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ On the complexity of matrix rank and rigidity ⋮ The Simple Reachability Problem in Switch Graphs ⋮ Planar and grid graph reachability problems ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ 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 ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ Basic Facts about Expander Graphs ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Combinatorial Algorithms for Distributed Graph Coloring ⋮ Energy Consumption of Group Search on a Line ⋮ Introducing Quasirandomness to Computer Science ⋮ An Improved Strategy for Exploring a Grid Polygon ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Weighted group search on a line \& implications to the priority evacuation problem ⋮ Unnamed Item
This page was built for publication: Undirected ST-connectivity in log-space
