Undirected connectivity in log-space

DOI10.1145/1391289.1391291zbMATH Open1315.68156DBLPjournals/jacm/Reingold08OpenAlexW2049516232WikidataQ55868768 ScholiaQ55868768MaRDI QIDQ3604402FDOQ3604402

Authors: Omer Reingold 

Publication date: 24 February 2009

Published in: Journal of the ACM (Search for Journal in Brave)

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

Recommendations

• Undirected ST-connectivity in log-space
• An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
• scientific article; zbMATH DE number 1559538
• Trading Space for Time in Undirected s-t Connectivity
• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)

Cited In (only showing first 100 items - show all)

• On probabilistic space-bounded machines with multiple access to random tape
• An algebraic characterization of testable Boolean CSPs
• Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
• On deterministic rendezvous at a node of agents with arbitrary velocities
• Incremental delay enumeration: space and time
• Pseudorandom generators for combinatorial checkerboards
• A general lower bound for collaborative tree exploration
• Anonymous meeting in networks
• The cycle switching graph of the Steiner triple systems of order 19 is connected
• Time versus cost tradeoffs for deterministic rendezvous in networks
• An improved lower bound for competitive graph exploration
• Drawing maps with advice
• The complexity of surjective homomorphism problems-a survey
• Interval graph representation with given interval and intersection lengths
• Counting perfect matchings and the switch chain
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• How much memory is needed for leader election
• Improved space efficient algorithms for BFS, DFS and applications
• Memory-constrained algorithms for simple polygons
• Constraint satisfaction with counting quantifiers
• Title not available (Why is that?)
• Gathering despite mischief
• Depth-first search in directed planar graphs, revisited
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• \(\text{RL}\subseteq \text{SC}\)
• The isomorphism problem for \(k\)-trees is complete for logspace
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Deterministic network exploration by a single agent with Byzantine tokens
• Byzantine gathering in polynomial time
• Space complexity of perfect matching in bounded genus bipartite graphs
• Solving linear equations parameterized by Hamming weight
• Undirected ST-connectivity in log-space
• A framework for in-place graph algorithms
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Space Complexity of Reachability Testing in Labelled Graphs
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• Green's theorem and isolation in planar graphs
• Rendezvous in networks in spite of delay faults
• Title not available (Why is that?)
• Depth-First Search Using $$O(n)$$ Bits
• Sublinear-space approximation algorithms for Max \(r\)-SAT
• How many ants does it take to find the food?
• On the complexity of inverse semigroup conjugacy
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
• Approximation in (Poly-) Logarithmic Space
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• Title not available (Why is that?)
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Choiceless Logarithmic Space
• Ontologies and Databases: The DL-Lite Approach
• Low-level dichotomy for quantified constraint satisfaction problems
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Gaming is a hard job, but someone has to do it!
• On the power of unambiguity in log-space
• Space complexity of reachability testing in labelled graphs
• Title not available (Why is that?)
• Reversibility in space-bounded computation
• Problems complete for deterministic logarithmic space
• Information and complexity in control systems: A tutorial
• Space-efficient biconnected components and recognition of outerplanar graphs
• The complexity of counting quantifiers on equality languages
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Log-space algorithms for paths and matchings in \(k\)-trees
• The complexity of properties of transformation semigroups
• Approximation in (poly-) logarithmic space
• Memory efficient algorithms for cactus graphs and block graphs
• Reprint of: Memory-constrained algorithms for simple polygons
• Expander construction in \(\mathsf{VNC}^1\)
• Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
• Title not available (Why is that?)
• The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
• Edge exploration of anonymous graph by mobile agent with external help
• The implication problem for functional dependencies and variants of marginal distribution equivalences
• Random walks on some basic classes of digraphs
• \(s\)-\(t\) connectivity on digraphs with a known stationary distribution
• Title not available (Why is that?)
• Temporal reachability minimization: delaying vs. deleting
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
• Robustness of the rotor-router mechanism
• Equivalence classes and conditional hardness in massively parallel computations
• On the isomorphism problem for decision trees and decision lists
• Complexity and enumeration in models of genome rearrangement
• Frameworks for designing in-place graph algorithms
• Title not available (Why is that?)
• STCON in directed unique-path graphs
• Different speeds suffice for rendezvous of two agents on arbitrary graphs
• Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
• Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
• Topology and Adjunction in Promise Constraint Satisfaction
• Byzantine gathering in polynomial time
• Consistent query answering for primary keys in Datalog
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Relaxed locally correctable codes
• From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
• Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas

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

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