@article{d56b829da2854c50b03aa4571201109b,
title = "Characteristics of the maximal independent set ZDD",
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.",
keywords = "Binary decision diagrams, Graph theory, Independent sets",
author = "Morrison, {David R.} and Sewell, {Edward C.} and Jacobson, {Sheldon Howard}",
note = "Funding Information: Acknowledgments The authors would like to thank two anonymous referees and the associate editor for their detailed review of our paper, which resulted in a significantly improved draft. The computational results reported were obtained at the Simulation and Optimization Laboratory at the University of Illinois, Urbana-Champaign. This research has been supported in part by the Air Force Office of Scientific Research (FA9550-10-1-0387), as well as fellowships through the National Defense Science & Engineering Graduate Fellowship (NDSEG) Program and National Science Foundation Graduate Research Fellowship Program. Additionally, the third author was supported in part by (while serving at) the National Science Foundation. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government.",
year = "2014",
month = jul,
doi = "10.1007/s10878-014-9722-4",
language = "English (US)",
volume = "28",
pages = "121--139",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "1",
}