Improved Space Efficient Algorithms for BFS, DFS and Applications

DOI10.1007/978-3-319-42634-1_10zbMath1477.68197arXiv1606.04718OpenAlexW2444631691MaRDI QIDQ2817855

Venkatesh Raman, Sankardeep Chakraborty, Niranka Banerjee

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.04718

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (8)

Space-efficient Euler partition and bipartite edge coloring ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ A Framework for In-place Graph Algorithms ⋮ Unnamed Item ⋮ Simple 2^f-Color Choice Dictionaries ⋮ Space efficient linear time algorithms for BFS, DFS and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-time trade-offs for stack-based algorithms
• Selection from read-only memory and sorting with minimum data movement
• Succinct data structures for searchable partial sums with optimal worst-case performance
• Upper bounds for time-space trade-offs in sorting and selection
• Selection and sorting with limited storage
• A simple test on 2-vertex- and 2-edge-connectivity
• Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
• $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
• Depth-First Search Using $$O(n)$$ Bits
• Space-efficient Basic Graph Algorithms
• New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
• Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
• Undirected connectivity in log-space
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Computational Complexity
• A Framework for Dynamizing Succinct Data Structures

This page was built for publication: Improved Space Efficient Algorithms for BFS, DFS and Applications