1 Search Results for "Kasahara, Shoji"

Document
DOI: 10.4230/LIPIcs.SEA.2018.21
Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams

Authors: Yu Nakahata, Jun Kawahara, and Shoji Kasahara

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{nakahata_et_al:LIPIcs.SEA.2018.21,
  author =	{Nakahata, Yu and Kawahara, Jun and Kasahara, Shoji},
  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 =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.21},
  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}
}
  • Refine by Author
  • 1 Kasahara, Shoji
  • 1 Kawahara, Jun
  • 1 Nakahata, Yu

  • Refine by Classification
  • 1 Mathematics of computing → Decision diagrams
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph enumeration

  • Refine by Keyword
  • 1 Decision diagram
  • 1 Enumeration problem
  • 1 Frontier-based search
  • 1 Graph algorithm
  • 1 Graph partitioning

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact