構造保証上の頂点被覆とフィードバック頂点集合【JST・京大機械翻訳】

Kellerhals Leon; Koana Tomohiro; Kunz Pascal

プレプリント

J-GLOBAL ID：202202208616141478 整理番号：22P0302537

構造保証上の頂点被覆とフィードバック頂点集合【JST・京大機械翻訳】

Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年03月11日プレプリントサーバーでの情報更新日： 2022年08月19日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

解法サイズkによってパラメータ化したVertex Coverは,五次必須固定パラメータ扱いやすい問題である。パラメータが小さいとき,FPTアルゴリズムは最も興味深い。k上のいくつかの下限は,マッチングの最大サイズのようなよく知られている。これは,解サイズkと下限の差によるVertex Coverのパラメータ化に関する研究のラインにつながった。問題がFPTであるような下限に対する最も顕著な事例は,マッチング数または最適分数LP解である。フィードバック頂点数,縮退,クラスタ削除数,およびツリー幅を含むkと他のグラフパラメータの間の差異によるパラメータ化を,前述の差異パラメタリゼーションのための固定パラメータ扱いやすさの境界を見つける目標で研究する。また,Feedback Vertex Set問題の類似のパラメタリゼーションを考察した。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , 【Automatic Indexing@JST】

グラフ理論基礎 , 計算理論

, ,

前のページに戻る