文献

J-GLOBAL ID：202202283355964396   整理番号：22A0000779

ATフリーグラフにおける誘導互いに素な経路【JST・京大機械翻訳】

Induced Disjoint Paths in AT-free graphs

著者 (3件)： Golovach Petr A. (Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway) ,  Paulusma Danieel (School of Engineering and Computing Sciences, Durham University, Science Laboratories, South Road, Durham DH1 3LE, UK) ,  van Leeuwen Erik Jan (Department of Information and Computing Sciences, Utrecht University, Princetonplein 5, 3584 CC Utrecht, The Netherlands)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 124  ページ： 170-191  発行年： 2022年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 経路P1,...,Pkは,2つの異なるPiとPjが共通頂点も隣接頂点(おそらくそれらの末端頂点を除く)も持たないならば,相互に誘導される。誘導障害経路問題は,特定の頂点(si,ti)のk対を持つグラフGが,各Piがsiとtiを接続するようなk相互誘導経路Piを含むかどうかを決定することである。この問題はk=2でもNP完全である。kが入力の部分であっても,ATフリーグラフに対して多項式時間で解くことができることを証明した。その結果,ATフリーグラフが誘導トポロジーマイナーとして固定グラフHを含むかどうかを決定する問題は多項式時間アルゴリズムである。著者らは,そのようなアルゴリズムが,ATフリーグラフのサブクラス,すなわち,コビパートトグラフに対してさえ,パラメータ|VH|を有するW[1]困難であることを証明することによって,本質的に最適であることを示した。また,k-a-Pathおよびk-in-Treeの問題は,kが入力の部分であっても,ATフリーグラフ上で多項式時間可解性であることを示した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  順路問題 ,  誘導障害
準シソーラス用語： 二部グラフ ,  決定可能性 ,  *互いに素 ,  多項式時間 ,  多項式時間アルゴリズム ,  NP完全性 , 【Automatic Indexing@JST】

著者キーワード (8件)： 互いに素な経路 ,  ATフリーグラフ ,  共二分グラフ ,  多項式時間アルゴリズム ,  W[1]硬度 ,  誘導トポロジーマイナー ,  k-in-a-Path ,  k-in-a-tree

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： グラフ ,  誘導 ,  互いに素 ,  経路