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

Hiroshi Iida

ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) from Otaru University of Commerce

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

Keywords: 組合せ最適化; 集合被覆; 頂点被覆; 近似アルゴリズム; 近似率 (search for similar items in EconPapers)
Pages: 4 pages
Date: 2007-12
References: Add references at CitEc
Citations:

Published in Discussion paper series (2007), 112: 1-4

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ota:busdis:10252/908

Access Statistics for this paper

More papers in ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) from Otaru University of Commerce Contact information at EDIRC.
Bibliographic data for series maintained by Miura, Chiho ().