講演抄録/キーワード |
講演名 |
2016-04-22 14:00
最小重み頂点被覆問題に対する高速な発見的手法の提案 ○清水悟司・山口一章・斎藤寿樹・増田澄男(神戸大) COMP2016-4 |
抄録 |
(和) |
各頂点に重みが付された無向グラフが与えられたとき,重みの和が
最小の頂点被覆を求める問題(MWVCP)は代表的な NP-困難問題の一つである.
本稿では,MWVCP に対する高速な発見的手法を提案する.提案法はリストヒュー
リスティックと呼ばれる単純な手法に基づく.計算機実験ではいくつかの近似ア
ルゴリズムとの比較を行い,提案法がそれらの近似アルゴリズムに比べ短い計算
時間で良い解を出力することを確認した. |
(英) |
Given an undirected graph with weight for each vertex, the minimum
weight vertex cover problem (MWVCP) is an NP-hard problem to find the
vertex cover of minimum weight. In this paper, a fast heuristic for
MWVCP is proposed. Our algorithm is based on a simple algorithm called
``list-heuristic''. Computational experiments show that our algorithm
calculates better solutions in shorter time than approximation
algorithms for MWVCP. |
キーワード |
(和) |
頂点被覆 / 独立集合 / クリーク / NP困難 / / / / |
(英) |
vertex cover / independent set / clique / np-hardness / / / / |
文献情報 |
信学技報, vol. 116, no. 17, COMP2016-4, pp. 23-28, 2016年4月. |
資料番号 |
COMP2016-4 |
発行日 |
2016-04-15 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-4 |