| 講演名 | 2003/11/18 最小節点ランキング全域木問題の計算複雑性について 宮田 敬三, 増山 繁, 中山 慎一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 最小節点ランキング全域木問題(MVRST)とは,与えられたグラフG上において,節点ランキングが最小となる全域木を求める問題である.本論文では,MVRSTがNP困難であることを示すために,3次元マッチング問題が,決定問題版のMVRSTへ多項式時間帰着可能であることを示す.その後,グラフGより直径lが最小となる全域木を切り出すことで,近似率([1/2(l+3)])/([log_2(l+2)])を達成できることを示す. |
| 抄録(英) | The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a ([1/2(l+3)])/([log_2(l+2)])-approximation algorithm for MVRST where l is the diameter of G. This approximation algorithm computes a spanning tree of G whose diameter is minimum. |
| キーワード(和) | 節点ランキング全域木 / 節点ランキング / NP困難 / 計算複雑性 |
| キーワード(英) | minimum vertex ranking spanning tree / vertex ranking / NP-hard / computational complexity |
| 資料番号 | COMP2003-55 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/11/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 最小節点ランキング全域木問題の計算複雑性について |
| サブタイトル（和） | |
| タイトル（英） | Computational complexity of the minimum vertex ranking spanning tree problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 節点ランキング全域木 / minimum vertex ranking spanning tree |
| キーワード(2)（和/英） | 節点ランキング / vertex ranking |
| キーワード(3)（和/英） | NP困難 / NP-hard |
| キーワード(4)（和/英） | 計算複雑性 / computational complexity |
| 第 1 著者 氏名（和/英） | 宮田 敬三 / Keizo MIYATA |
| 第 1 著者 所属（和/英） | 豊橋技術科学大学知識情報工学系 Knowkedge-Based Information Engineering, Toyohashi University of Technology |
| 第 2 著者 氏名（和/英） | 増山 繁 / Shigeru MASUYAMA |
| 第 2 著者 所属（和/英） | 豊橋技術科学大学知識情報工学系 Knowkedge-Based Information Engineering, Toyohashi University of Technology |
| 第 3 著者 氏名（和/英） | 中山 慎一 / Shin-ichi NAKAYAMA |
| 第 3 著者 所属（和/英） | 徳島大学総合科学部自然システム学科数理科学 Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima |
| 発表年月日 | 2003/11/18 |
| 資料番号 | COMP2003-55 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 468 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |