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

DOI10.1007/S10878-018-0270-1zbMATH Open1420.90076OpenAlexW2791769939MaRDI QIDQ2420652FDOQ2420652

Authors: 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

Recommendations

• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• scientific article; zbMATH DE number 1953077
• Space efficient linear time algorithms for BFS, DFS and applications
• Improved space efficient algorithms for BFS, DFS and applications
• Space-efficient basic graph algorithms

zbMATH Keywords

breadth-first searchdepth-first searchgraph algorithmschordal graphsmaximum cardinality search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Computational Complexity
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Undirected connectivity in log-space
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Selection and sorting with limited storage
• Reprint of: Memory-constrained algorithms for simple polygons
• A general label search to investigate classical graph search algorithms
• Maximal label search algorithms to compute perfect and minimal elimination orderings
• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• Improved space efficient algorithms for BFS, DFS and applications
• Depth-First Search Using $$O(n)$$ Bits
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• Biconnectivity, chain decomposition and \(st\)-numbering using \(O(n)\) bits
• Optimal time-space tradeoff for the 2D convex-hull problem
• Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
• A model classifying algorithms as inherently sequential with applications to graph searching
• New linear time algorithms for generating perfect elimination orderings of chordal graphs
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Space efficient linear time algorithms for BFS, DFS and applications

Cited In (7)

• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• Succinct data structure for path graphs
• Fast breadth-first search in still less space
• Succinct encodings for families of interval graphs
• Indexing graph search trees and applications
• Optimal In-place Algorithms for Basic Graph Problems
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420652)