| 講演名 | 2005-12-22 Max-Stretch Reduction for Tree Spanners 岩間 一雄, / 沖田 正樹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 木t-スパナーとは, グラフGの全域木でその伸長度がt以内(2つの頂点間の木上での距離がグラフ上での距離のt倍以内)であるものを言う. Gが木t-スパナーを持ち, 木t-1-スパナーを持たないとき, Gの伸長度がtであるという. 本稿ではグラフの伸長度を枝を追加して減少させる問題を議論する. 円グラフやグリッドグラフ等の特殊なグラフに対して最適な枝の追加アルゴリズムを与える. 一般のグラフに対しては問題は困難になるが, それでも, O(n/s')本の枝を追加して伸長度をs'にするアルゴリズムを与える. |
| 抄録(英) | A tree t-spanner T of a graph G is a spanning tree of G whose max-stretch is t, i.e., the distance between any two vertices in T is at most t times their distance in G. If G has a tree t-spanner but not a tree (t-1)-spanner, then G is said to have max-stretch of t. In this paper, we study the Max-Stretch Reduction Problem : for an unweighted graph G=(V, E), find a set of edges not in E originally whose insertion into G can decrease the max-stretch of G. Our results are as follows : (i) For a ring graph, we give a linear-time algorithm which inserts k edges improving the max-stretch optimally. (ii) For a grid graph, we give a nearly optimal max-stretch reduction algorithm which preserves the structure of the grid. (iii) In the general case, we show that it is NP-hard to decide, for a given graph G and its spanning tree of max-stretch t, whether or not one-edge insertion can decrease the max-stretch to t-1. (iv) Finally, we show that the max-stretch of an arbitrary graph on n vertices can be reduced to s'≧2 by inserting O(n/s') edges, which can be determined in linear time, and observe that this number of edges is optimal up to a constant. |
| キーワード(和) | 木スパナー / グラフの伸長度 / 円グラフ / グリッドグラフ / NP困難 |
| キーワード(英) | tree spanners / max-stretch / ring and grid graphs / NP-hard |
| 資料番号 | COMP2005-56 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/12/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Max-Stretch Reduction for Tree Spanners |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 木スパナー / tree spanners |
| キーワード(2)（和/英） | グラフの伸長度 / max-stretch |
| キーワード(3)（和/英） | 円グラフ / ring and grid graphs |
| キーワード(4)（和/英） | グリッドグラフ / NP-hard |
| キーワード(5)（和/英） | NP困難 |
| 第 1 著者 氏名（和/英） | 岩間 一雄 / Kazuo IWAMA |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | / 沖田 正樹 / Andrzej LINGAS |
| 第 2 著者 所属（和/英） | / 京都大学大学院情報学研究科 Department of Computer Science, Lund University |
| 発表年月日 | 2005-12-22 |
| 資料番号 | COMP2005-56 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 499 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |