| 講演名 | 2017-12-22 k-縮退グラフ中の支配集合の効率良い列挙 栗田 和宏(北大), 和佐 州洋(NII), 宇野 毅明(NII), 有村 博紀(北大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 支配集合はクリークや，独立点集合，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 |
| 資料番号 | ISEC2017-89,COMP2017-43 |
| 発行日 | 2017-12-14 (ISEC, COMP) |
| 研究会情報 | |
| 研究会 | ISEC / COMP |
|---|---|
| 開催期間 | 2017/12/21(から2日開催) |
| 開催地（和） | 高知工科大学永国寺キャンパス |
| 開催地（英） | Eikokuji Campus, Kochi University of Technology |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 委員長氏名（和） | 小川 一人(NHK) / 伊藤 大雄(電通大) |
| 委員長氏名（英） | Kazuto Ogawa(NHK) / Hiro Ito(Univ. of Electro-Comm.) |
| 副委員長氏名（和） | 藤岡 淳(神奈川大) / 盛合 志帆(NICT) / 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Atsushi Fujioka(Kanagawa Univ.) / Shiho Moriai(NICT) / Yushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 水木 敬明(東北大) / 大東 俊博(東海大) / 脊戸 和寿(成蹊大) / 斎藤 寿樹(九工大) |
| 幹事氏名（英） | Takaaki Mizuki(Tohoku Univ.) / Toshihiro Ohigashi(Tokai Univ.) / Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kyushu Inst. of Tech.) |
| 幹事補佐氏名（和） | 江村 恵太(NICT) / 駒野 雄一(東芝) / 須賀 祐治(インターネットイニシアティブ) |
| 幹事補佐氏名（英） | Keita Emura(NICT) / Yuichi Komano(TOSHIBA) / Yuuji Suga(IIJ) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Security / Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG-JTITLE |
| タイトル（和） | k-縮退グラフ中の支配集合の効率良い列挙 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Enumeration of Dominating Sets in K-Degenerate graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 支配集合 / dominating sets |
| キーワード(2)（和/英） | 列挙アルゴリズム / enumeration algorithm |
| キーワード(3)（和/英） | ならし多項式時間 / amorized polynomial time |
| キーワード(4)（和/英） | 縮退数 / degeneracy |
| 第 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) |
| 発表年月日 | 2017-12-22 |
| 資料番号 | ISEC2017-89,COMP2017-43 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | ISEC-369,COMP-370 |
| ページ範囲 | pp.111-117(ISEC), pp.111-117(COMP), |
| ページ数 | 7 |
| 発行日 | 2017-12-14 (ISEC, COMP) |