Undirected connectivity in log-space
From MaRDI portal
Publication:3604402
DOI10.1145/1391289.1391291zbMath1315.68156OpenAlexW2049516232WikidataQ55868768 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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (only showing first 100 items - show all)
Topology and Adjunction in Promise Constraint Satisfaction ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ An Algebraic Characterization of Testable Boolean CSPs ⋮ Unnamed Item ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ Unnamed Item ⋮ The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ On the complexity of inverse semigroup conjugacy ⋮ Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\) ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ Unnamed Item ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ Unnamed Item ⋮ Space Complexity of Reachability Testing in Labelled Graphs ⋮ How to meet asynchronously at polynomial cost ⋮ Information and complexity in control systems: A tutorial ⋮ Constraint Satisfaction with Counting Quantifiers ⋮ 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 ⋮ Counting Perfect Matchings and the Switch Chain ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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
This page was built for publication: Undirected connectivity in log-space
