| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-03-01 14:25 Power Vertex Cover問題の近似アルゴリズムについて 立松拓己・○林谷哲郎・藤戸敏弘（豊橋技科大）  COMP2019-50 |
|
| 抄録 | （和） | Vertex Cover を拡張するPower Vertex Cover 問題について，新たに2つの2倍近似アルゴリズムを提案 する． Power Vertex Cover では，グラフG = (V,E) に加え，各辺e ∈ E を被覆するために必要な重みとしてw(e) が 入力として与えられる． 辺e = {u, v} を被覆するためには，p(u) ≥ w(e) またはp(v) ≥ w(e) のいずれかを満たすよ うに， Power p ∈ R^V_+ を各頂点に割り当てる必要がある． Power Vertex Cover は，すべての辺を被覆するために割り当てられたPower の総和を最小化する問題であり，全ての辺e ∈ E についてw(e) = 1 である場合に通常のVertex Cover と一致する． 本稿では，同問題に対し，LP 緩和の丸め法および局所比定理に基づき，2種類の2倍近似アルゴリズムを提示する． |
| （英） | We present two 2-approximation algorithms for Power Vertex Cover problem, which is a generalization of the Vertex Cover problem. Given in Power Vertex Cover is a graph G = (V,E) with “edge” weights w(e), and an edge e = {u, v} is covered only if power p ∈ R ^V_+ assigned on the vertices satisfy either p(u) ≥ w(e) or p(v) ≥ w(e). We aim to find a power assignment of minimum sum that covers all edges in G. Clearly, Vertex Cover corresponds to Power Vertex Cover when all edge weights are equal to 1. In this paper, we present two 2-approximation algorithms for this problem, one designed based on LP rounding and the other based on the local ratio theorem. |
|
| キーワード | （和） | 頂点被覆問題 / グラフ理論 / 近似アルゴリズム / / / / / |
| （英） | Vertex Cover Problem / Graph Theory / Approximation Algorithms / / / / / | |
| 文献情報 | 信学技報, vol. 119, no. 433, COMP2019-50, pp. 29-33, 2020年3月. | |
| 資料番号 | COMP2019-50 | |
| 発行日 | 2020-02-23 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2019-50 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2020-03-01 - 2020-03-01 |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2020-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | Power Vertex Cover問題の近似アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On Approximation Algorithms for Power Vertex Cover Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 頂点被覆問題 / Vertex Cover Problem |
| キーワード(2)（和/英） | グラフ理論 / Graph Theory |
| キーワード(3)（和/英） | 近似アルゴリズム / Approximation Algorithms |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 立松 拓己 / Takumi Tatematsu / タテマツ タクミ |
| 第1著者 所属（和/英） | 豊橋技術科学大学 (略称： 豊橋技科大) Toyohashi University of Technology (略称： TUT) |
| 第2著者 氏名（和/英/ヨミ） | 林谷 哲郎 / Tetsuro Rintani / リンタニ テツロウ |
| 第2著者 所属（和/英） | 豊橋技術科学大学 (略称： 豊橋技科大) Toyohashi University of Technology (略称： TUT) |
| 第3著者 氏名（和/英/ヨミ） | 藤戸 敏弘 / Toshihiro Fujito / フジト トシヒロ |
| 第3著者 所属（和/英） | 豊橋技術科学大学 (略称： 豊橋技科大) Toyohashi University of Technology (略称： TUT) |
| 講演者 | 第2著者 |
| 発表日時 | 2020-03-01 14:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2019-50 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | no.433 |
| ページ範囲 | pp.29-33 |
| ページ数 | 5 |
| 発行日 | 2020-02-23 (COMP) |
[研究会発表申込システムのトップページに戻る]