アルゴリズムと計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:46 UTC 版)
「立方体グラフ」の記事における「アルゴリズムと計算量」の解説
何人かの研究者は、立方体グラフに限定された指数関数時間アルゴリズムの計算量についての研究を行っている。例えば、グラフのパス分解（英語版）に動的計画法を適用することにより、Fomin と Høie は時間 O(2n/6 + o(n)) 内に彼らの最大独立集合を見つける方法を示した。巡回セールスマン問題は、立方体グラフによって時間 O(1.251n) 内に解くことが出来る。 いくつかの重要なグラフ最適化問題はAPX困難である。すなわち、それらには近似率がある定数で評価されるような近似アルゴリズムが存在するが、（P=NPでない限り）近似率が 1 へと向かうような多項式時間近似スキームは存在しない。そのような問題には、最小の頂点被覆を見つける問題や最大独立集合、最小支配集合（英語版）、最大カットを見つける問題などが含まれる。立方体グラフの交叉数（英語版）（任意のグラフ描画（英語版）において交叉する辺の最小数）もまた、NP困難であるが、近似出来ることもある。
※この「アルゴリズムと計算量」の解説は、「立方体グラフ」の解説の一部です。
「アルゴリズムと計算量」を含む「立方体グラフ」の記事については、「立方体グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「アルゴリズムと計算量」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- アルゴリズムと計算量のページへのリンク
