| 講演名 | 2000/6/19 COMP2000-15 独立/連結な辺支配集合問題の近似可能性について 藤戸 敏弘, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では、辺支配集合に関連する問題の多項式時間近似特性について調べる。辺支配集合問題と最小極大マッチング問題は、一様辺重みの下では同じ近似特性を持ち、前者は、任意の重みの下でも2倍近似が可能であることが知られている。これに対し、最小重み極大マッチング問題を多項式時間計算可能な比率で近似することがNP-困難であることを示す。連結辺支配集合問題と連結点被覆問題も、一様辺重みの下では同じ近似特性を持ち、任意の重みの下でも、前者は3.598倍近似が可能であることが知られている。同問題の、(3+ε)倍近似アルゴリズムを示した後、最小重み連結点被覆問題が、(3+1n n)倍近似は可能であるが、NP⊂DTIME(n^<Ο(log log n)>)でない限り、(1-ε)1n n倍以下の近似は不可能であることを示す。 |
| 抄録(英) | We investigate polynomial-time approximability of the problems related to edge dominating sets of graphs. When edges are uniformly weighted, approximating the edge dominating set problem is polynomially equivalent to approximating the minimum maximal matching problem, and for the former problem it was recently found possible to do within a factor of 2 even with arbitrary weights. It will be shown, in contrast with this, that the minimum weight maximal matching problem cannot be approximated within any polynomially computable factor unless P=NP. The connected edge dominating set problem and the connected vertex cover problem also have the same approximability when edges/vertices are unit-weighted, and the former problem is known to be approximable, even with general edge weight, within a factor of 3.598. We will show that, when general weights are allowed, 1)the connected edge dominating set problem can be approximated within a factor of 3+ε, and 2)the connected vertex cover problem is approximable within a factor of 3+1n n but cannot be within(1-ε)1n n unless NP ⊂ DTIME(n^<Ο(log log n)>). |
| キーワード(和) | 辺支配集合 / 最小極大マッチング / 連結辺支配集合 / 連結点被覆 / 近似アルゴリズム |
| キーワード(英) | edge dominating set / minimum maximal matching / connected vertex cover / approximation algorithm |
| 資料番号 | COMP2000-15 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2000/6/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | COMP2000-15 独立/連結な辺支配集合問題の近似可能性について |
| サブタイトル（和） | |
| タイトル（英） | COMP2000-15 On Approximability of the Independent/Connected Edge Dominating Set Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 辺支配集合 / edge dominating set |
| キーワード(2)（和/英） | 最小極大マッチング / minimum maximal matching |
| キーワード(3)（和/英） | 連結辺支配集合 / connected vertex cover |
| キーワード(4)（和/英） | 連結点被覆 / approximation algorithm |
| キーワード(5)（和/英） | 近似アルゴリズム |
| 第 1 著者 氏名（和/英） | 藤戸 敏弘 / Toshihiro Fujito |
| 第 1 著者 所属（和/英） | 名古屋大学工学研究科電子工学専攻 Department of Electronics Nagoya University |
| 発表年月日 | 2000/6/19 |
| 資料番号 | COMP2000-15 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 144 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |