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

DOI10.1007/S10878-018-0270-1MaRDI QIDQ2420652zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

breadth-first searchdepth-first searchgraph algorithmschordal graphsmaximum cardinality search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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

Cites work

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

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)