問題タブ [vertex-cover]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - ブルートフォース頂点カバーアルゴリズムの最適化
次のような頂点カバーを解決するためのブルート フォース アルゴリズムを作成しています。
どこ
これを多くのグラフに試しています（ただし、最大サイズは20頂点です）。これには10年かかります...このブルートフォースで実行できる最適化はありますか？
algorithm - 頂点カバーの発見的解が最適解の最大 2 倍であることを示す
私が与えられたヒューリスティックな解決策は次のとおりです。
- グラフで深さ優先検索を実行する
- 葉をすべて削除する
- 残りのグラフは頂点カバーを形成します
「このヒューリスティックが、頂点カバーの最適解の最大 2 倍の大きさであることを示してください」という質問が与えられました。どうすればこれを表示できますか?
graph - このグラフ プロパティを理解できません
私は単純なグラフでそれを読みました |最小限の頂点カバー| <= 2*|最大一致|。
ここにグラフショーを考えてみましょう:-
ここで、最小の頂点カバーは {B,C,D,E} で、サイズは 4 で、最大一致のサイズはちょうど 1 です。したがって、4>2*1 であり、プロパティは満足していないようです。
誰かがこれで私を助けることができますか?
algorithm - 多項式時間で最大のマッチングを行うカーディナリティ頂点カバー
カーディナリティ頂点カバーの問題は、多項式時間での最大マッチングを使用して解決できますか? 近似係数とは何ですか? 私を助けてください
algorithm - ツリー貪欲アプローチの頂点カバー
質問: T をノード r をルートとする n ノード ツリーとします。T のすべてのエッジが保護されるように、T のノードにできるだけ少ないガードを配置する必要があります。これら 2 つのノード v の少なくとも 1 つにガードを配置すると、親ノード v とその子 w の間のエッジが保護されます。 、w。問題の最適解を見つけるための O(n) 時間アルゴリズムを与えてください。
私のアプローチは、ルートからポスト オーダー トラバーサルを行い、そのノードがリーフである場合を除いて、ガードされていないエッジの一部であるノードにガードを配置することでした...しかし、すべてのノードが配置されている場合、このアルゴリズムは機能しません。私のアルゴリズムは、チェーンの端を除くすべてのノードにガードを配置するためです。
私はオンラインで見て、DPソリューションをチェックアウトしましたが、これは私には理にかなっていますが、ツリーの頂点カバーを見つけるための貪欲なアルゴリズムがあるかどうか疑問に思っていました