エッジカット幅:エッジカットに基づくツリー幅のアルゴリズム駆動アナログ【JST・京大機械翻訳】

Brand Cornelius; Ceylan Esra; Hatschka Christian; Ganian Robert; Korchemna Viktoriia

プレプリント

J-GLOBAL ID：202202219101493160 整理番号：22P0296273

エッジカット幅:エッジカットに基づくツリー幅のアルゴリズム駆動アナログ【JST・京大機械翻訳】

Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

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

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

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

ツリー幅のような分解パラメータは一般にNP困難グラフ問題に対する固定パラメータアルゴリズムを得るために用いられる。ツリー幅によってパラメータ化されたW[1]困難である問題のために,自然な代替案は,頂点分離器の代わりにエッジカットに基づくツリー幅の適切なアナログを使用することである。ツリーカット幅がエッジカットの木幅の類似点としてコインされたが,そのアルゴリズム応用は,しばしば,エッジカットベースアナログによってパラメータ化された固定パラメータ扱いやすさをツリー幅に期待する12問題から,ツリーカット幅によってパラメータ化されたW[1]ハードであると,そのアルゴリズム応用は,しばしば,結果に導き出される。”1つは,木-カット幅によってパラメータ化されたW[1]-ハードである事を示したものである。”そのアルゴリズム的応用”は,しばしば,非点滅的結果に繋がった。”そのアルゴリズム的応用”は,木-切断幅によってパラメータ化された固定パラメータトライラビリティを期待する,という事をしばしば導く。主な貢献として,エッジカット幅と呼ばれるツリー幅に対するエッジカットベースアナログを開発した。エッジカット幅は,グラフのスパニング木を通過するサイクルの密度の測定に基づいて,直感的にである。その利益は,比較的単純な定義だけでなく,主に興味深いアルゴリズム特性を持ち,それは,固定パラメータアルゴリズムによって計算することができ,そして,それは,ツリーカット幅がそうでなくなるすべての前述の問題に対して,固定パラメータアルゴリズムをもたらした。【JST・京大機械翻訳】

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

グラフ理論基礎 , 計算理論 , パターン認識

, , ,

前のページに戻る