LIPIcs.SEA.2018.21.pdf
- Filesize: 0.49 MB
- 13 pages
Document
Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams
Authors
-
Part of:
Volume:
17th International Symposium on Experimental Algorithms (SEA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-19
Cite As Get 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)
0PDF Downloads
References
-
Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 100(8):677-691, 1986.
-
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.
-
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.
-
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.
-
Hiroaki Iwashita and Shin-ichi Minato. Efficient top-down ZDD construction techniques using recursive specifications. TCS Technical Reports, TCS-TR-A-13-69, 2013.
-
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.
-
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.
-
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.
- 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.
-
Donald E. Knuth. The art of computer programming, Vol. 4A, Combinatorial algorithms, Part 1. Addison-Wesley, 2011.
-
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.
-
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.
-
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).
-
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.
-
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.
-
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.