Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
From MaRDI portal
Publication:2420652
DOI10.1007/s10878-018-0270-1zbMath1420.90076OpenAlexW2791769939MaRDI QIDQ2420652
Sankardeep Chakraborty, Srinivasa Rao Satti
Publication date: 6 June 2019
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-018-0270-1
Related Items
Optimal In-place Algorithms for Basic Graph Problems, Succinct encodings for families of interval graphs, Succinct data structure for path graphs, Unnamed Item
Cites Work
- Reprint of: Memory-constrained algorithms for simple polygons
- A general label search to investigate classical graph search algorithms
- Selection and sorting with limited storage
- A model classifying algorithms as inherently sequential with applications to graph searching
- New linear time algorithms for generating perfect elimination orderings of chordal graphs
- Algorithmic graph theory and perfect graphs
- Space efficient linear time algorithms for BFS, DFS and applications
- Incidence matrices and interval graphs
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
- Depth-First Search Using $$O(n)$$ Bits
- Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Undirected connectivity in log-space
- Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Tight Lower Bounds for st-Connectivity on the NNJAG Model
- Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits
- Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
- Computational Complexity