| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2017-12-22 14:40 k-縮退グラフ中の支配集合の効率良い列挙 ○栗田和宏（北大）・和佐州洋・宇野毅明（NII）・有村博紀（北大）  ISEC2017-89 COMP2017-43 |
|
| 抄録 | （和） | 支配集合はクリークや，独立点集合，s-t パス，カットのように基本的なグラフ構造の一つである.クリー ク等のグラフ構造には極大や極小の構造を多項式遅延時間で列挙するアルゴリズムが知られている.しかし，極小支 配集合を多項式遅延もしくはならし多項式時間で列挙するアルゴリズムが存在するかどうかはわかっていない.さら に，極小でない支配集合を含めた全ての支配集合の列挙についてはあまり研究が行われていない.本論文では極小な 支配集合だけでなく，全ての支配集合の列挙を行う.主結果として，我々は効率の良い支配集合の列挙アルゴリズム を与える.このアルゴリズムは O (nm) 領域を用いて，全ての支配集合を解 1 つあたり O (k) 時間で列挙を行う.ここ で，k とは入力グラフの縮退数である.さらに，平面的グラフは縮退数が定数であることが知られている.したがっ て，提案アルゴリズムは平面的グラフ中の支配集合を解 1 つあたり定数時間で列挙する. |
| （英） | A dominating set is one of the fundamental graph structure, like clique, independent set, s-t path, and cut. It is known that there is a polynomial delay algorithm to enumerate theses minimal or maximal graph structures. However, it is open problem that there is a polynomial delay or amortized polynomial time algorithm to enumerate minimal dominating sets. In addition, enumeration of all dominating sets has not been paid much attention. In this paper, we enumerate all dominating sets not only minimal dominating sets. As a main result, we propose an efficient enumeration algorithm. This algorithm enumerates all dominating set in O (k) time per solution using O (nm) space, where k is degeneracy of an input graph. It is known that planar graphs have the constant degeneracy. Hence, the proposed algorithm enumerates all dominating set in constant time per solution. | |
| キーワード | （和） | 支配集合 / 列挙アルゴリズム / ならし多項式時間 / 縮退数 / / / / |
| （英） | dominating sets / enumeration algorithm / amorized polynomial time / degeneracy / / / / | |
| 文献情報 | 信学技報, vol. 117, no. 370, COMP2017-43, pp. 111-117, 2017年12月. | |
| 資料番号 | COMP2017-43 | |
| 発行日 | 2017-12-14 (ISEC, COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2017-89 COMP2017-43 |
|
| 研究会情報 | |
| 研究会 | ISEC COMP |
| 開催期間 | 2017-12-21 - 2017-12-22 |
| 開催地（和） | 高知工科大学永国寺キャンパス |
| 開催地（英） | Eikokuji Campus, Kochi University of Technology |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2017-12-ISEC-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | k-縮退グラフ中の支配集合の効率良い列挙 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Enumeration of Dominating Sets in K-Degenerate graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 支配集合 / dominating sets |
| キーワード(2)（和/英） | 列挙アルゴリズム / enumeration algorithm |
| キーワード(3)（和/英） | ならし多項式時間 / amorized polynomial time |
| キーワード(4)（和/英） | 縮退数 / degeneracy |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 栗田 和宏 / Kazuhiro Kurita / クリタ カズヒロ |
| 第1著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： HU) |
| 第2著者 氏名（和/英/ヨミ） | 和佐 州洋 / Kunihiro Wasa / ワサ クニヒロ |
| 第2著者 所属（和/英） | 国立情報学研究所 (略称： NII) National Institute of Informatics (略称： NII) |
| 第3著者 氏名（和/英/ヨミ） | 宇野 毅明 / Takeaki Uno / ウノ タケアキ |
| 第3著者 所属（和/英） | 国立情報学研究所 (略称： NII) National Institute of Informatics (略称： NII) |
| 第4著者 氏名（和/英/ヨミ） | 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ |
| 第4著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： HU) |
| 講演者 | 第1著者 |
| 発表日時 | 2017-12-22 14:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | ISEC2017-89, COMP2017-43 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | no.369(ISEC), no.370(COMP) |
| ページ範囲 | pp.111-117 |
| ページ数 | 7 |
| 発行日 | 2017-12-14 (ISEC, COMP) |
[研究会発表申込システムのトップページに戻る]