Undirected connectivity in log-space
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- \(\text{RL}\subseteq \text{SC}\)
- A fast randomized LOGSPACE algorithm for graph connectivity
- 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
- The implication problem for functional dependencies and variants of marginal distribution equivalences
- 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
- 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
- Anonymous meeting in networks
- Rendezvous in networks in spite of delay faults
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Sublinear-space approximation algorithms for Max r-SAT
- Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
- Improved space efficient algorithms for BFS, DFS and applications
- Random walks on some basic classes of digraphs
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- Reversibility in space-bounded computation
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- 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
- Solving linear equations parameterized by Hamming weight
- STCON in directed unique-path graphs
- Expanding Generating Sets for Solvable Permutation Groups
- s-t connectivity on digraphs with a known stationary distribution
- On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- Undirected ST-connectivity in log-space
- An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
- Ontologies and Databases: The DL-Lite Approach
- Problems complete for deterministic logarithmic space
- 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
- scientific article; zbMATH DE number 1559538 (Why is no real title available?)
- Formulas versus Circuits for Small Distance Connectivity
- Pseudorandomness via the discrete Fourier transform
- A fast randomized LOGSPACE algorithm for graph connectivity
- scientific article; zbMATH DE number 6866317 (Why is no real title available?)
- Expander construction in \(\mathsf{VNC}^1\)
- scientific article; zbMATH DE number 2086628 (Why is no real title available?)
- Gaming is a hard job, but someone has to do it!
- Interval graph representation with given interval and intersection lengths
- The complexity of properties of transformation semigroups
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Constant-round interactive proofs for delegating computation
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Byzantine gathering in polynomial time
- Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
- A framework for in-place graph algorithms
- Randomized and Symmetric Catalytic Computation
- Approximation in (Poly-) Logarithmic Space
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Simulating random walks on graphs in the streaming model
- Compressed Decision Problems in Hyperbolic Groups.
- Consistent query answering for primary keys in logspace
- Choiceless Logarithmic Space
- scientific article; zbMATH DE number 7561734 (Why is no real title available?)
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- scientific article; zbMATH DE number 7250165 (Why is no real title available?)
- Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
- The complexity of counting quantifiers on equality languages
- Deterministic approximation of random walks in small space
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)
