有界木幅グラフ上の一般化フィードバック頂点集合問題:単一指数パラメータ化アルゴリズムへの鍵【JST・京大機械翻訳】

Bonnet Edouard; Brettell Nick; Kwon O-joung; Marx Daniel

プレプリント

J-GLOBAL ID：202202201227734108 整理番号：21P0004192

有界木幅グラフ上の一般化フィードバック頂点集合問題:単一指数パラメータ化アルゴリズムへの鍵【JST・京大機械翻訳】

Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

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

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

著者 (4件)： , , ,
資料名：
発行年： 2017年04月22日プレプリントサーバーでの情報更新日： 2019年01月21日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

Feedback Vertex Setは,ツリー幅wのn-頂点グラフ上で時間2 ̄O(wlogw)n ̄O(1)で解くことができるが,最近,この実行時間が2 ̄O(w)n ̄O(1)に改善され,即ち,ツリー幅によってパラメータ化された単一指数である。Feedback Vertex Setの一般化を類似の実行時間で解くことができる。グラフのクラスPに対して,Bounded P-Block Vertex Desksは,n頂点と正の整数 ̄kと ̄dにグラフ ̄Gを与えられた場合,G-Sの各ブロックは,ほとんどのd頂点で,Pは,多項式時間で認識可能であり,そして,Pは,任意の自然遺伝条件を満たし,そして,Pは,時間2 ̄O(wd ̄2)n ̄O(1)で,Pが,時間2 ̄O(wd ̄2) ̄n ̄O(1)で,そして,Pが,時間2 ̄O(w_d ̄2) ̄n ̄O(1)で,そして,もしPが,時間2 ̄O(w_d ̄2) ̄n ̄O(1)で,そして,Pが,時間2 ̄O(w_d ̄2) ̄O(1)で,また,Pが,時間2 ̄O(w_d ̄2) ̄O(1)で,そして,Pまた,ターゲットグラフが小サイズのブロックよりも小さなサイズの連結成分を持ち,類似の結果を示す,Bounded P-Compent Vertex Expressionと呼ばれる類似問題を研究した。この問題のために,もしdが入力とPの一部がすべての弦グラフを含むならば,ETHが失敗するならば,いくつかの関数fのために時間f(w)n ̄o(w)で解決することができないことを示した。【JST・京大機械翻訳】

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

グラフ理論基礎

, , , , , ,

前のページに戻る