文献

J-GLOBAL ID：202202280913991909   整理番号：22A0797082

満足分割問題のパラメータ化計算量【JST・京大機械翻訳】

Parameterized complexity of satisfactory partition problem

著者 (3件)： Gaikwad Ajinkya (Indian Institute of Science Education and Research, Pune, India) ,  Maity Soumen (Indian Institute of Science Education and Research, Pune, India) ,  Tripathi Shuvam Kant (Indian Institute of Science Education and Research, Pune, India)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 907  ページ： 113-127  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 有向グラフGを与えられた場合,著者らは,目標がGの頂点集合を2つの部分に分割できるかどうか決定すること,すなわち,各頂点が,他の部分のようにそれ自身の部分において少なくとも多くの隣人であるかどうかを決定するのに,満足するパーティション問題を研究した。”その目的が,Gの頂点集合を2つの部分に分割できるかどうかを決定することである。”その目的”は,他の部分において,Gの頂点集合を2つの部分に分割できるかどうかを決定することである。バランスした満足するパーティション問題は上記の問題の変種であり,そこでは2つのパーサイトセットが同一の基数を持つのに必要である。両問題はNP完全であることが知られている。この問題は,GerberとKobler(2000)によって紹介され,他の著者によってさらに研究されたが,そのパラメータ化された複雑性は今までに未解決のままである。パラメータ化複雑性の観点からこの問題の理解を強化した。本論文の主な結果は次のものである。(1)満足な分割は,ブロックグラフに対して多項式時間可解性であり,(2)満足な分割とバランスした満足分割は,近隣多様性によってパラメータ化されたとき,固定パラメータ扱いやすい(FPT)である。(3)満足な分割とそのバランスしたバージョンは,有界クリーク幅のグラフのために多項式時間で解決することができて,(4)バランスした満足な分割は,ツリー幅によってパラメータ化したとき,W[1]ハードであった。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： グラフ ,  固定 ,  有向グラフ ,  *計算量 ,  *間仕切壁 ,  集合 ,  問題 ,  頂点 ,  パラメタリゼーション
準シソーラス用語： 決定可能性 ,  基数 ,  複雑性 ,  多項式時間 ,  有界 ,  パラメータ化計算量 , 【Automatic Indexing@JST】

著者キーワード (6件)： パラメータ化複雑性 ,  FPT ,  W[1]ハード ,  ツリー幅 ,  クリーク幅 ,  近傍多様性

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

タイトルに関連する用語 (3件)： 満足 ,  問題 ,  パラメータ化計算量