Recommendations
Cited in
(only showing first 100 items - show all)- An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity
- Approximation in (poly-) logarithmic space
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- The complexity of properties of transformation semigroups
- On probabilistic space-bounded machines with multiple access to random tape
- On deterministic rendezvous at a node of agents with arbitrary velocities
- Expander construction in \(\mathsf{VNC}^1\)
- Incremental delay enumeration: space and time
- An algebraic characterization of testable Boolean CSPs
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Pseudorandom generators for combinatorial checkerboards
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- scientific article; zbMATH DE number 7559089 (Why is no real title available?)
- Anonymous meeting in networks
- The cycle switching graph of the Steiner triple systems of order 19 is connected
- The implication problem for functional dependencies and variants of marginal distribution equivalences
- An improved lower bound for competitive graph exploration
- Random walks on some basic classes of digraphs
- Edge exploration of anonymous graph by mobile agent with external help
- A general lower bound for collaborative tree exploration
- s-t connectivity on digraphs with a known stationary distribution
- Time versus cost tradeoffs for deterministic rendezvous in networks
- Drawing maps with advice
- The complexity of surjective homomorphism problems-a survey
- On the parameterized complexity of computing tree-partitions
- Interval graph representation with given interval and intersection lengths
- List colouring trees in logarithmic space
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Temporal reachability minimization: delaying vs. deleting
- scientific article; zbMATH DE number 7536562 (Why is no real title available?)
- How much memory is needed for leader election
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Counting perfect matchings and the switch chain
- Derandomization of quantum algorithm for triangle finding
- Improved space efficient algorithms for BFS, DFS and applications
- Memory-constrained algorithms for simple polygons
- Dispersion of mobile robots on graphs in the asynchronous model
- On the parameterized complexity of computing tree-partitions
- scientific article; zbMATH DE number 7754308 (Why is no real title available?)
- Constraint satisfaction with counting quantifiers
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Equivalence classes and conditional hardness in massively parallel computations
- Robustness of the rotor-router mechanism
- Depth-first search in directed planar graphs, revisited
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- The isomorphism problem for \(k\)-trees is complete for logspace
- On the isomorphism problem for decision trees and decision lists
- \(\text{RL}\subseteq \text{SC}\)
- Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
- Gathering despite mischief
- Traversal-invariant characterizations of logarithmic space
- Frameworks for designing in-place graph algorithms
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Complexity and enumeration in models of genome rearrangement
- Deterministic network exploration by a single agent with Byzantine tokens
- scientific article; zbMATH DE number 7250165 (Why is no real title available?)
- Byzantine gathering in polynomial time
- Space complexity of perfect matching in bounded genus bipartite graphs
- Solving linear equations parameterized by Hamming weight
- STCON in directed unique-path graphs
- Small-space spectral sparsification via bounded-independence sampling
- Different speeds suffice for rendezvous of two agents on arbitrary graphs
- Undirected ST-connectivity in log-space
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- A framework for in-place graph algorithms
- Explicit construction of \(q+1\) regular local Ramanujan graphs, for all prime-powers \(q\)
- Green's theorem and isolation in planar graphs
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- How to meet when you forget: log-space rendezvous in arbitrary graphs
- Rendezvous in networks in spite of delay faults
- Constant depth circuit complexity for generating quasigroups
- Topology and Adjunction in Promise Constraint Satisfaction
- Logical expressibility of syntactic NL for complementarity and maximization
- Depth-First Search Using O(n) Bits
- Space Complexity of Reachability Testing in Labelled Graphs
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- Byzantine gathering in polynomial time
- Consistent query answering for primary keys in Datalog
- Unambiguous, randomized, and symmetric catalytic computation
- Sublinear-space approximation algorithms for Max r-SAT
- Pseudorandom generators for unbounded-width permutation branching programs
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Deterministic approximation of random walks in small space
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
- Parameterized complexities of dominating and independent set reconfiguration
- Relaxed locally correctable codes
- Symmetries and complexity (invited talk)
- Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
- Graph exploration: the impact of a distance constraint
- Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs
- Spectral sparsification via bounded-independence sampling
- On expander graphs and connectivity in small space
- How many ants does it take to find the food?
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Constant workspace algorithms for computing relative hulls in the plane
- Space efficient algorithm for solving reachability using tree decomposition and separators
- The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
- On the complexity of inverse semigroup conjugacy
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)
