講演名 | 2019-09-02 平面グラフの省領域分離アルゴリズム 渡辺 治(東工大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 平面グラフ分離定理とは,「任意の n の平面グラフ G は,必ず O(n^{1/2}) 頂点のセパレーター集合 S を持つ」という主張である.ただし,S の頂点を G から取り除くと,ほぼ同じ大きさで非連結な部分グラフに分割されるとき,S は G のセパレーター集合と呼ばれる.そのようなセパレータ集合を計算するアルゴリズムをセパレーター・アルゴリズムと呼ぶ.この報告では,「劣線形時間」かつ多項式時間で求めるセパレーター・アルゴリズム設計のために,著者らが開発した2つのアルゴリズムを紹介する. |
抄録(英) | The Separator Theorem states that any planar graph G with n vertices has a separator of size O(n^{1/2}), that is, a set S of O(n^{1/2}) vertices of G such that by removing S, G is split into disconnected subgraphs of almost equal size, say, each having more than n/3 vertices. A separator algorithm is an algorithm that computes a separator for a given planar graph. We explain two algorithms that have been developed recently by the author and his colleagues for designing a ``sublinear-space'' and polynomial-time separator algorithm. |
キーワード(和) | 平面グラフ / 平面グラフ分離定理 / 劣線形領アルゴリズム / 多項式時間アルゴリズム |
キーワード(英) | planar graph / separator theorem / sublinear-space algorithm / polynomial-time algorithm |
資料番号 | COMP2019-13 |
発行日 | 2019-08-26 (COMP) |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2019/9/2(から1日開催) |
開催地(和) | 岡山大学 津島キャンパス |
開催地(英) | Tsushima Campus, Okayama University |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | 藤戸 敏弘(豊橋技科大) |
委員長氏名(英) | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
副委員長氏名(和) | 中野 眞一(群馬大) |
副委員長氏名(英) | Shinichi Nakano(Gunma Univ.) |
幹事氏名(和) | 大舘 陽太(熊本大) / 玉置 卓(兵庫県立大) |
幹事氏名(英) | Yota Otachi(Kumamoto Univ) / Suguru Tamaki(Univ. of Hyogo) |
幹事補佐氏名(和) | 脊戸 和寿(成蹊大) |
幹事補佐氏名(英) | Kazuhisa Seto(Seikei Univ.) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
---|---|
本文の言語 | ENG-JTITLE |
タイトル(和) | 平面グラフの省領域分離アルゴリズム |
サブタイトル(和) | |
タイトル(英) | Space efficient separator algorithms for planar graphs |
サブタイトル(和) | |
キーワード(1)(和/英) | 平面グラフ / planar graph |
キーワード(2)(和/英) | 平面グラフ分離定理 / separator theorem |
キーワード(3)(和/英) | 劣線形領アルゴリズム / sublinear-space algorithm |
キーワード(4)(和/英) | 多項式時間アルゴリズム / polynomial-time algorithm |
第 1 著者 氏名(和/英) | 渡辺 治 / Osamu Watanabe |
第 1 著者 所属(和/英) | 東京工業大学(略称:東工大) Tokyo Institute of Technology(略称:Tokyo Inst. of Tech.) |
発表年月日 | 2019-09-02 |
資料番号 | COMP2019-13 |
巻番号(vol) | vol.119 |
号番号(no) | COMP-191 |
ページ範囲 | pp.17-24(COMP), |
ページ数 | 8 |
発行日 | 2019-08-26 (COMP) |