| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-10-26 15:55 ［依頼講演］SEA2018発表報告および最近の研究について ○中畑 裕・川原 純（奈良先端大）  COMP2018-29 |
|
| 抄録 | （和） | グラフを複数の連結成分にバランスよく分割する問題は様々な応用を持つ． 多目的な問題においては，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 / / / | |
| 文献情報 | 信学技報, vol. 118, no. 268, COMP2018-29, pp. 57-57, 2018年10月. | |
| 資料番号 | COMP2018-29 | |
| 発行日 | 2018-10-19 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-29 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2018-10-26 - 2018-10-26 |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2018-10-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | SEA2018発表報告および最近の研究について |
| サブタイトル（和） | |
| タイトル（英） | Report of Presentation in SEA2018 and Recent Study |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフアルゴリズム / Graph algorithm |
| キーワード(2)（和/英） | グラフ分割 / Graph partitioning |
| キーワード(3)（和/英） | 決定グラフ / Decision diagram |
| キーワード(4)（和/英） | フロンティア法 / Frontier-based search |
| キーワード(5)（和/英） | 列挙問題 / Enumeration problem |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 中畑 裕 / Yu Nakahata / ナカハタ ユウ |
| 第1著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第2著者 氏名（和/英/ヨミ） | 川原 純 / Jun Kawahara / カワハラ ジュン |
| 第2著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 講演者 | 第1著者 |
| 発表日時 | 2018-10-26 15:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-29 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.268 |
| ページ範囲 | p.57 |
| ページ数 | 1 |
| 発行日 | 2018-10-19 (COMP) |
[研究会発表申込システムのトップページに戻る]