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

Sankardeep Chakraborty () and Srinivasa Rao Satti ()
Additional contact information
Sankardeep Chakraborty: National Institute of Informatics
Srinivasa Rao Satti: Seoul National University

Journal of Combinatorial Optimization, 2019, vol. 37, issue 2, No 5, 465-481

Abstract: Abstract Following the recent trends of designing space efficient algorithms for fundamental algorithmic graph problems, we present several time-space tradeoffs for performing maximum cardinality search (MCS), stack breadth first search, and queue breadth first search on a given input graph. As applications of these results, we also provide space-efficient implementations for testing if a given undirected graph is chordal, reporting an independent set, and a proper coloring of a given chordal graph among others. Finally, we also show how two other seemingly different graph problems and their algorithms have surprising connection with MCS with respect to designing space efficient algorithms.

Keywords: Maximum cardinality search; Graph algorithms; Breadth-first search; Depth-first search; Chordal graphs (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0270-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:2:d:10.1007_s10878-018-0270-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0270-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().