頂点被覆へのリスト減少法の解析に関する一考察

頂点被覆は, NP 困難な組合せ最適化問題ゆえに, 多項式時間では解き得ないと考えられている. 他方, 頂点被覆にはいくつかの近似解法が提案されている. これら近似解法には, 大きく分けて二種類, 即ち, 与えられたグラフの最大次数をΔ として近似率O(log Δ) を与えるものと近似率2 を与えるものがある. 近年, この頂点被覆に対するある近似解法が, 近似率√Δ/2+3/2を与えることが示された. ここでは, その近似率を導出した解析に若干の修正を加えて, より良い近似率を導くことを試みる.

MoreLess

Year of publication:	2007-12
Authors:	Iida, Hiroshi
Institutions:	Department of Economics, Otaru University of Commerce
Subject:	組合せ最適化 \| 集合被覆 \| 頂点被覆 \| 近似アルゴリズム \| 近似率

More details

Extent:	application/pdf
Series:	ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation).
Type of publication:	Book / Working Paper
Notes:	Published in Discussion paper series (2007), 112: 1-4 4 pages
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010965515