Recommendations
Cited in
(only showing first 100 items - show all)- Identifiability of graphs with small color classes by the Weisfeiler-Leman algorithm
- The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
- Approximation in (Poly-) Logarithmic Space
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Topology-hiding computation on all graphs
- Graph isomorphism restricted by lists
- scientific article; zbMATH DE number 1559538 (Why is no real title available?)
- Formulas versus Circuits for Small Distance Connectivity
- Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
- Space-efficient algorithms for reachability in directed geometric graphs
- Ontologies and Databases: The DL-Lite Approach
- Space efficient linear time algorithms for BFS, DFS and applications
- Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
- Choiceless Logarithmic Space
- On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace
- scientific article; zbMATH DE number 2086628 (Why is no real title available?)
- Low-level dichotomy for quantified constraint satisfaction problems
- Randomized and Symmetric Catalytic Computation
- Expanderizing higher-order random walks
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- Estimating the number of connected components in sublinear time
- Reachability in graphs having linear 2-arboricity two is \(\mathsf{NL}\)-hard
- On locally-characterized expander graphs (a survey)
- The complexity of computing the period and the exponent of a digraph
- Constant-round interactive proofs for delegating computation
- Complexity and enumeration in models of genome rearrangement
- A further study on weak Byzantine gathering of mobile agents
- The complexity of bidirected reachability in valence systems
- Gaming is a hard job, but someone has to do it!
- scientific article; zbMATH DE number 7561734 (Why is no real title available?)
- Collision-free exploration by mobile agents using pebbles
- Distance-restricted firefighting on finite graphs
- PSPACE-completeness of Bloxorz and of games with 2-buttons
- Expanding Generating Sets for Solvable Permutation Groups
- Searching without communicating: tradeoffs between performance and selection complexity
- On the power of unambiguity in log-space
- scientific article; zbMATH DE number 6866317 (Why is no real title available?)
- Expander construction in \(\mathrm{VNC}^1\)
- On the parameterized complexity of freezing dynamics
- Random walks on rotating expanders
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Compressed Decision Problems in Hyperbolic Groups.
- scientific article; zbMATH DE number 7650109 (Why is no real title available?)
- The parallel dynamic complexity of the abelian Cayley group membership problem
- Space complexity of reachability testing in labelled graphs
- The parameterized space complexity of embedding along a path
- On the complexity of rolling block, colour, and Alice mazes
- \(\tilde{O}(n^{1/3})\)-space algorithm for the grid graph reachability problem
- Constant work-space algorithms for facility location problems
- The ANTS problem
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- On the constant-depth circuit complexity of generating quasigroups
- scientific article; zbMATH DE number 7561483 (Why is no real title available?)
- Want to gather? No need to chatter!
- Network robustness depth and topology management of networked dynamic systems
- Decision problems for reversible and permutation automata
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Reversibility in space-bounded computation
- Expanderizing higher-order random walks
- Planarity testing revisited
- Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
- Sparse high dimensional expanders via local lifts
- Pseudorandomness via the discrete Fourier transform
- Problems complete for deterministic logarithmic space
- Space-efficient biconnected components and recognition of outerplanar graphs
- The complexity of counting quantifiers on equality languages
- Information and complexity in control systems: A tutorial
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Log-space algorithms for paths and matchings in k-trees
- Exploration of carrier-based time-varying networks: the power of waiting
- Reprint of: Memory-constrained algorithms for simple polygons
- Memory efficient algorithms for cactus graphs and block graphs
- 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
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)
