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

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

プレプリント

J-GLOBAL ID：202202210500751702 整理番号：22P0294207

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

Induced Disjoint Paths and Connected Subgraphs for $H$-Free Graphs

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

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

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

グラフG=(V,E)における経路P_1,P_kは,もし2つの異なるP_iとP_jが共通頂点も隣接頂点も持たないならば,相互に誘導される。誘導障害経路問題は,特定の頂点のk対を持つグラフG(s_i,t_i)が,各P_iがs_iから始まり,t_iで終わるようなk相互誘導経路P_iを含むかどうかを決定することである。これはk=2に対してもNP完全である古典的グラフ問題である。著者らは,端末の接続対の代わりに,自然一般化,誘導障害結合部分グラフを導入し,端末のセットを接続しなければならない。Hフリーグラフに対する両方の問題の計算複雑性のほとんど完全な二分性を与え,それは,誘導部分グラフとしていくつかの固定グラフHを含まないグラフである。最後に,端末集合の数kが固定されるならば,入力の一部ではなく,第二問題の複雑性の完全な分類を与えた。【JST・京大機械翻訳】

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

グラフ理論基礎

, , , ,

前のページに戻る