文献

J-GLOBAL ID：202002231445096696   整理番号：20A1344968

[数式:原文を参照]経路パッキングのパラメータ化複雑性【JST・京大機械翻訳】

Parameterized Complexity of [Formula : see text]-Path Packing

著者 (9件)： Belmonte Remy (The University of Electro-Communications, Chofu, Tokyo, Japan) ,  Hanaka Tesshu (Chuo University, Bunkyo-ku, Tokyo, Japan) ,  Kanzaki Masaaki (Kumamoto University, Kumamoto, Japan) ,  Kiyomi Masashi (Yokohama City University, Yokohama, Japan) ,  Kobayashi Yasuaki (Kyoto University, Kyoto, Japan) ,  Kobayashi Yusuke (Kyoto University, Kyoto, Japan) ,  Lampis Michael (Universite Paris-Dauphine, PSL University, CNRS, LAMSADE, Paris, France) ,  Ono Hirotaka (Nagoya University, Nagoya, Japan) ,  Otachi Yota (Nagoya University, Nagoya, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12126  ページ： 43-55  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフ[数式:原文を参照],[数式:原文を参照],および整数kと[数式:原文を参照]を与えられたとき,[数式:原文を参照]-Path Packing問題は,[数式:原文を参照]のAと内部点におけるエンドポイントを持つ長さ[数式:原文を参照]のk頂点-互いに素経路を見つける。パラメータ|A|,[数式:原文を参照],k,ツリー幅,経路幅,およびそれらの組合せによるこの問題のパラメータ化複雑性を研究した。これらのパラメータに関して鋭い複雑性コントラストを示した。他の結果の中で,この問題は[数式:原文を参照]の場合に多項式時間可解性であり,一方,一定[数式:原文を参照]に対してはNP完全であることを示した。また,この問題は,経路幅[数式:原文を参照]によってパラメータ化されたW[1]ハードであり,一方,それは,ツリー幅[数式:原文を参照]によってパラメータ化された固定パラメータであった。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *コントラスト ,  パラメタリゼーション
準シソーラス用語： 決定可能性 ,  互いに素 ,  エンドポイント ,  複雑性 ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (3件)： A経路パッキング ,  固定パラメータトラクトビリティ ,  ツリー幅

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 数式 ,  参照 ,  経路 ,  パラメータ化 ,  複雑性