Characteristics of the maximal independent set ZDD

被引：0
|
作者：
David R. Morrison
Edward C. Sewell
Sheldon H. Jacobson
机构：
[1] Univerisity of Illinois,Department of Computer Science
[2] Urbana-Champaign,Department of Mathematics and Statistics
[3] Southern Illinois University,Department of Computer Science
[4] Edwardsville,undefined
[5] Univerisity of Illinois,undefined
[6] Urbana-Champaign,undefined
来源：
Journal of Combinatorial Optimization | 2014年 / 28卷
关键词：
Independent sets; Graph theory; Binary decision diagrams;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：121 / 139
页数：18
相关论文
共 50 条
  • [1] Characteristics of the maximal independent set ZDD
    Morrison, David R.
    Sewell, Edward C.
    Jacobson, Sheldon H.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 28 (01) : 121 - 139
  • [2] Beeping a Maximal Independent Set
    Afek, Yehuda
    Alon, Noga
    Bar-Joseph, Ziv
    Cornejo, Alejandro
    Haeupler, Bernhard
    Kuhn, Fabian
    DISTRIBUTED COMPUTING, 2011, 6950 : 32 - +
  • [3] Beeping a maximal independent set
    Afek, Yehuda
    Alon, Noga
    Bar-Joseph, Ziv
    Cornejo, Alejandro
    Haeupler, Bernhard
    Kuhn, Fabian
    DISTRIBUTED COMPUTING, 2013, 26 (04) : 195 - 208
  • [4] Algorithms of maximal independent set
    Zhu, Songnian
    Zhu, Qiang
    Xinan Jiaotong Daxue Xuebao/Journal of Southwest Jiaotong University, 1995, 30 (04): : 473 - 479
  • [5] Beeping a maximal independent set
    Yehuda Afek
    Noga Alon
    Ziv Bar-Joseph
    Alejandro Cornejo
    Bernhard Haeupler
    Fabian Kuhn
    Distributed Computing, 2013, 26 : 195 - 208
  • [6] Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
    Balliu, Alkida
    Brandt, Sebastian
    Kuhn, Fabian
    Olivetti, Dennis
    PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, : 2632 - 2676
  • [7] Local Computation of Maximal Independent Set
    Ghaffari, Mohsen
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 438 - 449
  • [8] Local Computation of Maximal Independent Set
    Ghaffari, Mohsen
    arXiv, 2022,
  • [9] Finding a maximal weighted independent set in wireless networks
    Basagni, S
    TELECOMMUNICATION SYSTEMS, 2001, 18 (1-3) : 155 - 168
  • [10] A NEW PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM
    GOLDBERG, M
    SPENCER, T
    SIAM JOURNAL ON COMPUTING, 1989, 18 (02) : 419 - 427
12345