License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.21
URN: urn:nbn:de:0030-drops-89560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8956/
Go to the corresponding LIPIcs Volume Portal

Nakahata, Yu ; Kawahara, Jun ; Kasahara, Shoji

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

pdf-format:
LIPIcs-SEA-2018-21.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{nakahata_et_al:LIPIcs:2018:8956,
  author =	{Yu Nakahata and Jun Kawahara and Shoji Kasahara},
  title =	{{Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8956},
  URN =		{urn:nbn:de:0030-drops-89560},
  doi =		{10.4230/LIPIcs.SEA.2018.21},
  annote =	{Keywords: Graph algorithm, Graph partitioning, Decision diagram, Frontier-based search, Enumeration problem}
}

Keywords: Graph algorithm, Graph partitioning, Decision diagram, Frontier-based search, Enumeration problem
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI