Depth-First Search Using O(n) Bits
From MaRDI portal
Depth-First Search Using $$O(n)$$ Bits
Recommendations
- scientific article; zbMATH DE number 1069483
- scientific article; zbMATH DE number 3990867
- scientific article; zbMATH DE number 3949734
- Depth-first search with P systems
- The number of depth-first searches of an ordered set
- A random NC algorithm for depth first search
- Planar Depth-First Search in O(\log n) Parallel Time
- Depth-First Mini-Bucket Elimination
- scientific article; zbMATH DE number 140499
Cites work
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- A random NC algorithm for depth first search
- Depth-First Search and Linear Graph Algorithms
- Depth-first search is inherently sequential
- Embedding and canonizing graphs of bounded genus in logspace
- Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
- Parallelism and the maximal path problem
- Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
- Priority queues and sorting for read-only data
- Time-space tradeoffs for all-nearest-larger-neighbors problems
- Undirected connectivity in log-space
- \(\widetilde{O}(\sqrt{n})\)-space and polynomial-time algorithm for planar directed graph reachability
Cited in
(29)- Approximation in (poly-) logarithmic space
- Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism
- Simple 2f-Color Choice Dictionaries
- Improved space efficient algorithms for BFS, DFS and applications
- Space-efficient basic graph algorithms
- Biconnectivity, chain decomposition and st-numbering using O(n) bits
- Depth-first search in directed planar graphs, revisited
- Extra space during initialization of succinct data structures and dynamical initializable arrays
- Space-efficient Euler partition and bipartite edge coloring
- Frameworks for designing in-place graph algorithms
- Space-efficient vertex separators for treewidth
- A framework for in-place graph algorithms
- Space-efficient algorithms for longest increasing subsequence
- Space-efficient algorithms for longest increasing subsequence
- Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
- scientific article; zbMATH DE number 1069483 (Why is no real title available?)
- The number of depth-first searches of an ordered set
- Space-efficient graph coarsening with applications to succinct planar encodings
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Space-efficient algorithms for reachability in directed geometric graphs
- Space efficient linear time algorithms for BFS, DFS and applications
- scientific article; zbMATH DE number 3990867 (Why is no real title available?)
- Indexing graph search trees and applications
- Optimal In-place Algorithms for Basic Graph Problems
- Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
- scientific article; zbMATH DE number 3949734 (Why is no real title available?)
- Space-efficient biconnected components and recognition of outerplanar graphs
This page was built for publication: Depth-First Search Using $$O(n)$$ Bits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942660)
