Characteristics of the maximal independent set ZDD

David R. Morrison, Edward C. Sewell, Sheldon Howard Jacobson

Research output: Contribution to journalArticlepeer-review

Abstract

Zero-suppressed binary decision diagrams (ZDDs) are important data structures that are used in a number of combinatorial optimization settings. This paper explores a ZDD characterization for the maximal independent sets of a graph; a necessary and sufficient condition for when nodes in the ZDD can be merged is provided, and vertex orderings of the graph are studied to determine which orderings produce smaller ZDDs. A bound on the width of the maximal independent set ZDD is obtained, relating it to the Fibonacci numbers. Finally, computational results are reported.

Original languageEnglish (US)
Pages (from-to)121-139
Number of pages19
JournalJournal of Combinatorial Optimization
Volume28
Issue number1
DOIs
StatePublished - Jul 2014

Keywords

  • Binary decision diagrams
  • Graph theory
  • Independent sets

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Characteristics of the maximal independent set ZDD'. Together they form a unique fingerprint.

Cite this