WEKO3
アイテム
頂点被覆へのリスト減少法の解析に関する一考察
http://hdl.handle.net/10252/908
http://hdl.handle.net/10252/9083bd312aa-d33f-4fab-a934-48c91825f9a4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
no112.pdf (186.2 kB)
|
|
| Item type | テクニカルレポート / Technical Report(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2008-06-17 | |||||
| タイトル | ||||||
| タイトル | 頂点被覆へのリスト減少法の解析に関する一考察 | |||||
| 言語 | ja | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| キーワード | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 組合せ最適化 | |||||
| キーワード | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 集合被覆 | |||||
| キーワード | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 頂点被覆 | |||||
| キーワード | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 近似アルゴリズム | |||||
| キーワード | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 近似率 | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||
| 資源タイプ | technical report | |||||
| 著者 |
飯田, 浩志
× 飯田, 浩志 |
|||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 7735 | |||||
| 姓名 | Iida, Hiroshi | |||||
| 言語 | en | |||||
| bibliographic_information |
en : Discussion paper series 巻 112, p. 1-4, 発行日 2007-12 |
|||||
| 出版者 | ||||||
| 出版者 | 小樽商科大学ビジネス創造センター | |||||
| 言語 | ja | |||||
| 出版タイプ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
| 日本十進分類法 | ||||||
| 言語 | ja | |||||
| 主題Scheme | NDC | |||||
| 主題 | 410 | |||||
| NIIサブジェクト | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 数学 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 頂点被覆は, NP 困難な組合せ最適化問題ゆえに, 多項式時間では解き得ないと考えられている. 他方, 頂点被覆にはいくつかの近似解法が提案されている. これら近似解法には, 大きく分けて二種類, 即ち, 与えられたグラフの最大次数をΔ として近似率O(log Δ) を与えるものと近似率2 を与えるものがある. 近年, この頂点被覆に対するある近似解法が, 近似率√Δ/2+3/2を与えることが示された. ここでは, その近似率を導出した解析に若干の修正を加えて, より良い近似率を導くことを試みる. |
|||||
| 言語 | ja | |||||
