Undirected connectivity in log-space
From MaRDI portal
Publication:3604402
DOI10.1145/1391289.1391291zbMath1315.68156WikidataQ55868768 ScholiaQ55868768MaRDI QIDQ3604402
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
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Related Items
Unnamed Item, Unnamed Item, Formulas versus Circuits for Small Distance Connectivity, Pseudorandomness via the Discrete Fourier Transform, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, The complexity of properties of transformation semigroups, Unnamed Item, Unnamed Item, Unnamed Item, Constant-Round Interactive Proofs for Delegating Computation, Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm, Unnamed Item, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, How to meet asynchronously at polynomial cost, Constraint Satisfaction with Counting Quantifiers, Counting Perfect Matchings and the Switch Chain, Anonymous meeting in networks, Solving linear equations parameterized by Hamming weight, Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, Derandomizing the HSSW algorithm for 3-SAT, Log-space algorithms for paths and matchings in \(k\)-trees, Reprint of: Memory-constrained algorithms for simple polygons, Pseudorandom generators for combinatorial checkerboards, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Drawing maps with advice, Deterministic network exploration by a single agent with Byzantine tokens, Space complexity of perfect matching in bounded genus bipartite graphs, The complexity of surjective homomorphism problems-a survey, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Gaming is a hard job, but someone has to do it!, Interval graph representation with given interval and intersection lengths, The complexity of counting quantifiers on equality languages, Memory efficient algorithms for cactus graphs and block graphs, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, 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, 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, Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, An improved lower bound for competitive graph exploration, How many ants does it take to find the food?, On deterministic rendezvous at a node of agents with arbitrary velocities, A gentle introduction to applications of algorithmic metatheorems for space and circuit classes, On the power of unambiguity in log-space, How to meet when you forget: log-space rendezvous in arbitrary graphs, Low-level dichotomy for quantified constraint satisfaction problems, Consistent query answering for primary keys in Datalog, Approximation in (Poly-) logarithmic space, Equivalence classes and conditional hardness in massively parallel computations, Byzantine gathering in polynomial time, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, Depth-first search in directed planar graphs, revisited, Expander construction in \(\mathrm{VNC}^1\), Constant work-space algorithms for facility location problems, Exploration of carrier-based time-varying networks: the power of waiting, Frameworks for designing in-place graph algorithms, Estimating the number of connected components in sublinear time, Incremental delay enumeration: space and time, Space complexity of reachability testing in labelled graphs, Space efficient linear time algorithms for BFS, DFS and applications, On the isomorphism problem for decision trees and decision lists, Byzantine gathering in networks, Memory-constrained algorithms for simple polygons, The ANTS problem, Searching without communicating: tradeoffs between performance and selection complexity, 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, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, Network robustness depth and topology management of networked dynamic systems, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Rendezvous in networks in spite of delay faults, Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences, Improved Space Efficient Algorithms for BFS, DFS and Applications, Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems, Reversibility in space-bounded computation, Depth-First Search Using $$O(n)$$ Bits, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape, PSPACE-Completeness of Bloxorz and of Games with 2-Buttons, Different Speeds Suffice for Rendezvous of Two Agents on Arbitrary Graphs, A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, Planarity Testing Revisited, Expanding Generating Sets for Solvable Permutation Groups, On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace, Ontologies and Databases: The DL-Lite Approach, The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems, An Algebraic Characterization of Testable Boolean CSPs, Unnamed Item, Unnamed Item, Unnamed Item, Space Complexity of Reachability Testing in Labelled Graphs, Information and complexity in control systems: A tutorial, Topology-hiding computation on all graphs, A general lower bound for collaborative tree exploration, Time versus cost tradeoffs for deterministic rendezvous in networks, Graph isomorphism restricted by lists
