講演抄録/キーワード |
講演名 |
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 |