Undirected connectivity in log-space
From MaRDI portal
Publication:3604402
Recommendations
Cited in
(only showing first 100 items - show all)- Green's theorem and isolation in planar graphs
- The cycle switching graph of the Steiner triple systems of order 19 is connected
- How to meet when you forget: log-space rendezvous in arbitrary graphs
- Information and complexity in control systems: A tutorial
- A framework for in-place graph algorithms
- Ontologies and Databases: The DL-Lite Approach
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Time versus cost tradeoffs for deterministic rendezvous in networks
- On probabilistic space-bounded machines with multiple access to random tape
- Rendezvous in networks in spite of delay faults
- Depth-first search in directed planar graphs, revisited
- Space complexity of perfect matching in bounded genus bipartite graphs
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Constraint satisfaction with counting quantifiers
- An improved lower bound for competitive graph exploration
- On the power of unambiguity in log-space
- Drawing maps with advice
- scientific article; zbMATH DE number 1559538 (Why is no real title available?)
- Deterministic network exploration by a single agent with Byzantine tokens
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- Sublinear-space approximation algorithms for Max \(r\)-SAT
- An algebraic characterization of testable Boolean CSPs
- The complexity of surjective homomorphism problems-a survey
- Problems complete for deterministic logarithmic space
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- Improved space efficient algorithms for BFS, DFS and applications
- The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
- Pseudorandom generators for combinatorial checkerboards
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Depth-First Search Using $$O(n)$$ Bits
- Byzantine gathering in polynomial time
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Counting perfect matchings and the switch chain
- Memory-constrained algorithms for simple polygons
- Space-efficient biconnected components and recognition of outerplanar graphs
- Gaming is a hard job, but someone has to do it!
- How many ants does it take to find the food?
- Log-space algorithms for paths and matchings in \(k\)-trees
- On deterministic rendezvous at a node of agents with arbitrary velocities
- Incremental delay enumeration: space and time
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- The isomorphism problem for \(k\)-trees is complete for logspace
- \(\text{RL}\subseteq \text{SC}\)
- Solving linear equations parameterized by Hamming weight
- Approximation in (Poly-) Logarithmic Space
- Interval graph representation with given interval and intersection lengths
- A general lower bound for collaborative tree exploration
- Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
- Low-level dichotomy for quantified constraint satisfaction problems
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- The complexity of counting quantifiers on equality languages
- The complexity of properties of transformation semigroups
- scientific article; zbMATH DE number 7561483 (Why is no real title available?)
- Reversibility in space-bounded computation
- Approximation in (poly-) logarithmic space
- How much memory is needed for leader election
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Memory efficient algorithms for cactus graphs and block graphs
- Reprint of: Memory-constrained algorithms for simple polygons
- Space complexity of reachability testing in labelled graphs
- Anonymous meeting in networks
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Undirected ST-connectivity in log-space
- Gathering despite mischief
- On the complexity of inverse semigroup conjugacy
- Choiceless Logarithmic Space
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- Space Complexity of Reachability Testing in Labelled Graphs
- Expander construction in \(\mathrm{VNC}^1\)
- Complexity and enumeration in models of genome rearrangement
- Random walks on some basic classes of digraphs
- Searching without communicating: tradeoffs between performance and selection complexity
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Equivalence classes and conditional hardness in massively parallel computations
- Expander construction in \(\mathsf{VNC}^1\)
- Estimating the number of connected components in sublinear time
- Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
- scientific article; zbMATH DE number 2086628 (Why is no real title available?)
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- STCON in directed unique-path graphs
- \(s\)-\(t\) connectivity on digraphs with a known stationary distribution
- On expander graphs and connectivity in small space
- Consistent query answering for primary keys in Datalog
- On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- PSPACE-completeness of Bloxorz and of games with 2-buttons
- On the parameterized complexity of freezing dynamics
- Random walks on rotating expanders
- Formulas versus Circuits for Small Distance Connectivity
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Relaxed locally correctable codes
- Randomized and Symmetric Catalytic Computation
- A further study on weak Byzantine gathering of mobile agents
- On the isomorphism problem for decision trees and decision lists
- Space efficient linear time algorithms for BFS, DFS and applications
- Space-efficient algorithms for reachability in directed geometric graphs
- An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
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)
