Depth-First Search Using $$O(n)$$ Bits

DOI10.1007/978-3-319-13075-0_44zbMath1430.68172OpenAlexW2284006119MaRDI QIDQ2942660

Pascal Schweitzer, Matsuo Konagaya, Masashi Kiyomi, Yota Otachi, Taisuke Izumi, Hirotaka Ono, Jun Tarui, Ryuhei Uehara, Tetsuo Asano

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_44

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Optimal In-place Algorithms for Basic Graph Problems, Space-efficient Euler partition and bipartite edge coloring, Space-efficient vertex separators for treewidth, Depth-first search in directed planar graphs, revisited, Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits, Space-Efficient Algorithms for Longest Increasing Subsequence, Space-efficient algorithms for reachability in directed geometric graphs, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Sorting and ranking of self-delimiting numbers with applications to tree isomorphism, Space-efficient biconnected components and recognition of outerplanar graphs, Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays., Frameworks for designing in-place graph algorithms, A Framework for In-place Graph Algorithms, Space-efficient algorithms for longest increasing subsequence, Approximation in (Poly-) logarithmic space, Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster, Improved Space Efficient Algorithms for BFS, DFS and Applications, Simple 2^f-Color Choice Dictionaries, Space efficient linear time algorithms for BFS, DFS and applications

Cites Work

• Unnamed Item
• Depth-first search is inherently sequential
• Parallelism and the maximal path problem
• A random NC algorithm for depth first search
• Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
• $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
• Undirected connectivity in log-space
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
• Priority Queues and Sorting for Read-Only Data
• Embedding and canonizing graphs of bounded genus in logspace
• Depth-First Search and Linear Graph Algorithms
• Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search