Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams

Authors Yu Nakahata, Jun Kawahara, Shoji Kasahara



PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.21.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Yu Nakahata
  • Nara Institute of Science and Technology, Ikoma, Japan
Jun Kawahara
  • Nara Institute of Science and Technology, Ikoma, Japan
Shoji Kasahara
  • Nara Institute of Science and Technology, Ikoma, Japan

Cite AsGet BibTex

Yu Nakahata, Jun Kawahara, and Shoji Kasahara. Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SEA.2018.21

Abstract

Partitioning a graph into balanced components is important for several applications. For multi-objective problems, it is useful not only to find one solution but also to enumerate all the solutions with good values of objectives. However, there are a vast number of graph partitions in a graph, and thus it is difficult to enumerate desired graph partitions efficiently. In this paper, an algorithm to enumerate all the graph partitions such that all the weights of the connected components are at least a specified value is proposed. To deal with a large search space, we use zero-suppressed binary decision diagrams (ZDDs) to represent sets of graph partitions and we design a new algorithm based on frontier-based search, which is a framework to directly construct a ZDD. Our algorithm utilizes not only ZDDs but also ternary decision diagrams (TDDs) and realizes an operation which seems difficult to be designed only by ZDDs. Experimental results show that the proposed algorithm runs up to tens of times faster than an existing state-of-the-art algorithm.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Graph enumeration
  • Mathematics of computing → Decision diagrams
Keywords
  • Graph algorithm
  • Graph partitioning
  • Decision diagram
  • Frontier-based search
  • Enumeration problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 100(8):677-691, 1986. Google Scholar
  2. Gary Hardy, Corinne Lucet, and Nikolaos Limnios. K-terminal network reliability measures with binary decision diagrams. IEEE Transactions on Reliability, 56(3):506-515, 2007. Google Scholar
  3. Hiroshi Imai, Kyoko Sekine, and Keiko Imai. Computational investigations of all-terminal network reliability via BDDs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E82-A:714-721, 1999. Google Scholar
  4. Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi. Distribution loss minimization with guaranteed error bound. IEEE Transactions on Smart Grid, 5(1):102-111, 2014. Google Scholar
  5. Hiroaki Iwashita and Shin-ichi Minato. Efficient top-down ZDD construction techniques using recursive specifications. TCS Technical Reports, TCS-TR-A-13-69, 2013. Google Scholar
  6. Jun Kawahara, Takashi Horiyama, Keisuke Hotta, and Shin-ichi Minato. Generating all patterns of graph partitions within a disparity bound. In Proc. of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM), pages 119-131, 2017. Google Scholar
  7. Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 100(9):1773-1784, 2017. Google Scholar
  8. Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka. Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs. In Computational Intelligence in Information Systems, pages 294-305, 2017. Google Scholar
  9. Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka. Enumerating all subgraphs without forbidden induced subgraphs via multivalued decision diagrams. CoRR, 2018. URL: http://arxiv.org/abs/1804.03822.
  10. Donald E. Knuth. The art of computer programming, Vol. 4A, Combinatorial algorithms, Part 1. Addison-Wesley, 2011. Google Scholar
  11. Takanori Maehara, Hirofumi Suzuki, and Masakazu Ishihata. Exact computation of influence spread by binary decision diagrams. In Proc. of the 26th International World Wide Conference (WWW), pages 947-956, 2017. Google Scholar
  12. Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proc. of the 30th ACM/IEEE design automation conference, pages 272-277, 1993. Google Scholar
  13. Yu Nakahata, Jun Kawahara, Takashi Horiyama, and Shoji Kasahara. Enumerating all spanning shortest path forests with distance and capacity constraints. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (to appear). Google Scholar
  14. Kyoko Sekine, Hiroshi Imai, and Seiichiro Tani. Computing the Tutte polynomial of a graph of moderate size. In Proc. of the 6th International Symposium on Algorithms and Computation (ISAAC), pages 224-233, 1995. Google Scholar
  15. Koichi Yasuoka. A new method to represent sets of products: ternary decision diagrams. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 78(12):1722-1728, 1995. Google Scholar
  16. Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato. Finding all solutions and instances of numberlink and slitherlink by ZDDs. Algorithms, 5(2):176-213, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail