| 講演名 | 2018-10-26 ［依頼講演］SEA2018発表報告および最近の研究について 中畑 裕(奈良先端大), 川原 純(奈良先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | グラフを複数の連結成分にバランスよく分割する問題は様々な応用を持つ．多目的な問題においては，1つの解を見つけるだけでなくよい目的関数値を持つ解を複数列挙することが有用である．しかし，グラフの分割の方法は膨大に存在するため，所望のグラフ分割のみを効率よく列挙することは難しい．本研究では，与えられたグラフの分割であって，各連結成分の重みが指定した範囲内にあるようなもののみを効率よく列挙するアルゴリズムを提案する．膨大な探索空間を扱うため，本研究ではゼロサプレス型二分決定グラフ（ZDD）を用いてグラフ分割の集合を効率よく表現する．また，提案手法はZDDだけでなく三分決定グラフ（TDD）を併用することでZDDのみでは難しかった操作を実現する．計算機実験により，既存手法より数十倍高速にZDDを構築できることを示す．本発表では国際会議SEA2018にて行った発表を報告し，最近の研究について紹介する． |
| 抄録(英) | 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 the desired graph partitions efficiently. In this presentation, 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. In the presentation, we report our presentation in SEA2018 and talk about the recent study. |
| キーワード(和) | グラフアルゴリズム / グラフ分割 / 決定グラフ / フロンティア法 / 列挙問題 |
| キーワード(英) | Graph algorithm / Graph partitioning / Decision diagram / Frontier-based search / Enumeration problem |
| 資料番号 | COMP2018-29 |
| 発行日 | 2018-10-19 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/10/26(から1日開催) |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［依頼講演］SEA2018発表報告および最近の研究について |
| サブタイトル（和） | |
| タイトル（英） | [Invited Lecture] Report of Presentation in SEA2018 and Recent Study |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフアルゴリズム / Graph algorithm |
| キーワード(2)（和/英） | グラフ分割 / Graph partitioning |
| キーワード(3)（和/英） | 決定グラフ / Decision diagram |
| キーワード(4)（和/英） | フロンティア法 / Frontier-based search |
| キーワード(5)（和/英） | 列挙問題 / Enumeration problem |
| 第 1 著者 氏名（和/英） | 中畑 裕 / Yu Nakahata |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 2 著者 氏名（和/英） | 川原 純 / Jun Kawahara |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 発表年月日 | 2018-10-26 |
| 資料番号 | COMP2018-29 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-268 |
| ページ範囲 | pp.57-57(COMP), |
| ページ数 | 1 |
| 発行日 | 2018-10-19 (COMP) |