Improved Space Efficient Algorithms for BFS, DFS and Applications
From MaRDI portal
Publication:2817855
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
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