Undirected connectivity in log-space

DOI10.1145/1391289.1391291zbMath1315.68156OpenAlexW2049516232WikidataQ55868768 ScholiaQ55868768MaRDI QIDQ3604402

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

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ Byzantine gathering in networks ⋮ Randomized and Symmetric Catalytic Computation ⋮ An improved lower bound for competitive graph exploration ⋮ On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace ⋮ Rendezvous in networks in spite of delay faults ⋮ Expander Construction in VNC1 ⋮ Expanding Generating Sets for Solvable Permutation Groups ⋮ Solving linear equations parameterized by Hamming weight ⋮ Byzantine gathering in polynomial time ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Memory-constrained algorithms for simple polygons ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Reversibility in space-bounded computation ⋮ The ANTS problem ⋮ Searching without communicating: tradeoffs between performance and selection complexity ⋮ Depth-first search in directed planar graphs, revisited ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Robustness of the rotor-router mechanism ⋮ The parameterized space complexity of embedding along a path ⋮ Derandomizing the HSSW algorithm for 3-SAT ⋮ On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ Depth-First Search Using $$O(n)$$ Bits ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ On the power of unambiguity in log-space ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ PSPACE-Completeness of Bloxorz and of Games with 2-Buttons ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Network robustness depth and topology management of networked dynamic systems ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ Unnamed Item ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ Constant work-space algorithms for facility location problems ⋮ How many ants does it take to find the food? ⋮ How to meet when you forget: log-space rendezvous in arbitrary graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Low-level dichotomy for quantified constraint satisfaction problems ⋮ Exploration of carrier-based time-varying networks: the power of waiting ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Drawing maps with advice ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ On deterministic rendezvous at a node of agents with arbitrary velocities ⋮ Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ The cycle switching graph of the Steiner triple systems of order 19 is connected ⋮ How much memory is needed for leader election ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ Gaming is a hard job, but someone has to do it! ⋮ Interval graph representation with given interval and intersection lengths ⋮ A gentle introduction to applications of algorithmic metatheorems for space and circuit classes ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Planarity Testing Revisited ⋮ The complexity of counting quantifiers on equality languages ⋮ Memory efficient algorithms for cactus graphs and block graphs ⋮ Estimating the number of connected components in sublinear time ⋮ Green's theorem and isolation in planar graphs ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Incremental delay enumeration: space and time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Consistent query answering for primary keys in Datalog ⋮ Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences ⋮ Approximation in (Poly-) logarithmic space ⋮ The complexity of properties of transformation semigroups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ Unnamed Item ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Ontologies and Databases: The DL-Lite Approach ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Choiceless Logarithmic Space ⋮ Space complexity of reachability testing in labelled graphs ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm ⋮ Unnamed Item ⋮ The implication problem for functional dependencies and variants of marginal distribution equivalences ⋮ Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems ⋮ On the isomorphism problem for decision trees and decision lists ⋮ Anonymous meeting in networks

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