Hフリーグラフのための少数誘導互いに素な経路【JST・京大機械翻訳】

Martin Barnaby; Paulusma Danieel; Smith Siani; van Leeuwen Erik Jan

プレプリント

J-GLOBAL ID：202202205325584748 整理番号：22P0299969

Hフリーグラフのための少数誘導互いに素な経路【JST・京大機械翻訳】

Few Induced Disjoint Paths for $H$-Free Graphs

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

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

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

グラフG=(V,E)における経路P ̄1,P ̄kは,もし2つの明確なP ̄iとP ̄jが共通の頂点も隣接頂点も持たないならば,相互に誘導される。固定整数kに対して,k-Induced Disjoint Paths問題は,特定の頂点(s_i,t_i)のk対を持つグラフGが,各P ̄iがs_iから始まり,t_iで終わるようなk相互誘導経路P ̄iを含むかどうかを決定することである。非誘導バージョンは,あらゆる固定整数kに対して多項式時間可解性であるとよく知られているが,文献状態からの古典的結果は,2誘導障害経路でさえNP完全である。入力がHフリーグラフに制約されるならば,誘導部分グラフとして固定グラフHのないグラフであるならば,k-誘導障害経路のための新しい複雑性結果を証明した。これらの結果を,kが入力の部分である,誘導障害経路に対する複雑性二分法と比較した。【JST・京大機械翻訳】

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

グラフ理論基礎

, , ,

前のページに戻る