| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-12-03 16:35 最大支配問題 宮野英次（九工大）・○小野廣隆（九大）  COMP2010-46 |
|
| 抄録 | （和） | グラフにおける頂点/辺支配集合問題の新しい亜種について考える．ある頂点はその頂点自身と隣接点を支配すると言い，同様にある辺はその辺自身と隣接する辺を支配すると言う．グラフ$G = (V,E)$ と正整数$k$ が与えられたとき，$k$-頂点($k$-辺) 支配問題( それぞれ以下$k$-MaxVD, $k$-MaxED と呼ぶ) は高々サイズ$k$ の頂点の部分集合$D_V\subseteq V$ (または辺の部分集合$D_E\subseteq E$) の中で，支配する頂点集合（また辺集合）のサイズを最大化するものを求める問題である．本論文では，まずこの問題に対して単純な貪欲アルゴリズムが$k$-MaxVD，$k$-MaxED いずれに対しても近似比($1-1/e$)を達成することを示す．次に$P \neq NP$ の条件下で，$k$-MaxVDに対してこの近似比が多項式時間アルゴリズムの最善であることを示す．さらに$P \neq NP$の条件下で，$k$-MaxED に対して$1303/1304$ よりも良い近似比の多項式時間アルゴリズムが存在しないことを示す．一方，$k$ がグラフの最小最大マッチングのサイズを超えないという条件下では，$k$-MaxED に対して近似比$3/4$ の多項式時間アルゴリズムが存在することを示す． |
| （英） | We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to {\em dominate} itself and its all adjacent vertices, and similarly an edge is said to {\em dominate} itself and its all adjacent edges. Given an input graph $G = (V, E)$ and an integer $k$, the {\sc $k$-Vertex ($k$-Edge) Maximum Domination} ({\sf $k$-MaxVD} and {\sf $k$-MaxED}, respectively) is to find a subset $D_{V} \subseteq V$ of vertices (resp., $D_{E}\subseteq E$ of edges) with size at most $k$ that maximizes the cardinality of dominated vertices (resp., edges). In this paper, we first show that a simple greedy strategy achieves an approximation ratio of $(1-1/e)$ for both {\sf $k$-MaxVD} and {\sf $k$-MaxED}. Then, we show that this approximation ratio is the best possible for {\sf $k$-MaxVD} unless ${\cal P} = {\cal NP}$. We also prove that, for any constant $\varepsilon > 0$, there is no polynomial time $1303/1304 + \varepsilon$ approximation algorithm for {\sf $k$-MaxED} unless ${\cal P} = {\cal NP}$. However, if $k$ is not larger than the size of the minimum maximal matching, {\sf $k$-MaxED} is $3/4$-approximable in polynomial time. |
|
| キーワード | （和） | 支配集合 / 近似アルゴリズム / 近似不可能性 / / / / / |
| （英） | Dominating set / Approximation algorithm / Inapproximability / / / / / | |
| 文献情報 | 信学技報, vol. 110, no. 325, COMP2010-46, pp. 53-60, 2010年12月. | |
| 資料番号 | COMP2010-46 | |
| 発行日 | 2010-11-26 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2010-46 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-12-03 - 2010-12-03 |
| 開催地（和） | 九州工業大学 Kyutechプラザ |
| 開催地（英） | Kyutech Plaza, Kyushu Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-12-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 最大支配問題 |
| サブタイトル（和） | |
| タイトル（英） | Maximum Domination Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 支配集合 / Dominating set |
| キーワード(2)（和/英） | 近似アルゴリズム / Approximation algorithm |
| キーワード(3)（和/英） | 近似不可能性 / Inapproximability |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 宮野 英次 / Eiji Miyano / ミヤノ エイジ |
| 第1著者 所属（和/英） | 九州工業大学 (略称： 九工大) Kyushu Institute of Technology (略称： Kyushu Inst. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ |
| 第2著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu university (略称： Kyushu Univ.) |
| 講演者 | 第2著者 |
| 発表日時 | 2010-12-03 16:35:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2010-46 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.325 |
| ページ範囲 | pp.53-60 |
| ページ数 | 8 |
| 発行日 | 2010-11-26 (COMP) |
[研究会発表申込システムのトップページに戻る] (日本語ページの行間係数: 1)