Undirected connectivity in log-space

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

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)

• Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
• Approximation in (Poly-) logarithmic space
• 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
• How to meet asynchronously at polynomial cost
• 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
• A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
• How much memory is needed for leader election
• Memory-constrained algorithms for simple polygons
• Title not available (Why is that?)
• 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
• On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• Deterministic network exploration by a single agent with Byzantine tokens
• Space complexity of perfect matching in bounded genus bipartite graphs
• Byzantine gathering in networks
• Solving linear equations parameterized by Hamming weight
• Undirected ST-connectivity in log-space
• Improved Space Efficient Algorithms for BFS, DFS and Applications
• 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
• Constraint Satisfaction with Counting Quantifiers
• 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
• 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
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• An Algebraic Characterization of Testable Boolean CSPs
• Derandomizing the HSSW algorithm for 3-SAT
• Gaming is a hard job, but someone has to do it!
• On the power of unambiguity in log-space
• Counting Perfect Matchings and the Switch Chain
• Space complexity of reachability testing in labelled graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reversibility in space-bounded computation
• Title not available (Why is that?)
• 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
• A Framework for In-place Graph Algorithms
• The complexity of properties of transformation semigroups
• Memory efficient algorithms for cactus graphs and block graphs
• Reprint of: Memory-constrained algorithms for simple polygons
• On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace
• 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
• Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
• Title not available (Why is that?)
• Temporal reachability minimization: delaying vs. deleting
• Title not available (Why is that?)
• Title not available (Why is that?)
• Planarity Testing Revisited
• Title not available (Why is that?)
• Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm
• 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
• Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
• Frameworks for designing in-place graph algorithms
• Title not available (Why is that?)
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Pseudorandomness via the Discrete Fourier Transform
• Title not available (Why is that?)
• Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
• Topology and Adjunction in Promise Constraint Satisfaction
• Title not available (Why is that?)
• Byzantine gathering in polynomial time
• Consistent query answering for primary keys in Datalog

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)