Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS

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

zbMATH Keywords

graph algorithmschordal graphsdepth-first searchbreadth-first searchmaximum cardinality search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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