文献

J-GLOBAL ID：202002268806529291   整理番号：20A0193070

密なハイパーグラフにおける完全マッチングとパッキングの複雑さ【JST・京大機械翻訳】

The complexity of perfect matchings and packings in dense hypergraphs

著者 (2件)： Han Jie (Department of Mathematics, University of Rhode Island, Kingston, RI, 02881, USA) ,  Treglown Andrew (School of Mathematics, University of Birmingham, Birmingham, B15 2TT, UK)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 141  ページ： 72-104  発行年： 2020年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 2つのk-グラフHとFを与えて,Hにおける完全なF-パッキングは,HにおけるFの頂点-非結合コピーの収集であり,それは一緒にHにおけるすべての頂点をカバーした。Fが単一エッジである場合,完全なFパッキングは単純に完全なマッチングである。与えられた固定Fに対しては,n頂点kグラフHが完全なFパッキングを含むかどうかの決定問題がNP完全である場合が多い。実際に,もしk≧3ならば,完全な照合のための対応する問題はNP完全であるが,k=2ならば,Fが少なくとも3つの頂点から成る成分を持つ場合,問題はNP完全である。本論文では,完全Fパッキングのための対応する決定問題が多項式時間可解である(ハイパー)グラフのクラスを決定するために使用できる一般的ツールを与えた。次に,このツールの3つの応用を与えた。(i)Given1≦l≦k-1では,この条件を満たすkグラフが完全な整合を持つかどうかを決定するために多項式時間可解である最小l-度条件を与える。(ii)グラフFを用いて,この条件を満たすグラフが完全なFパッキングを持つかどうかを決定するために多項式時間可解である最小次数条件を与えた。(iii)Kがk部分kグラフであるkグラフにおける完全Kパッキングに対する類似結果も証明した。lの値の範囲に対して,k(i)はKeevash,KnoxおよびMycroftの予測を解決する。(ii)負におけるYushuの質問に答える。一方,(iii)Keevashの結果を一般化した。多くの場合,著者らの結果は,最小次数条件を低下させるという意味で,対応する決定問題がNP完全になるという意味で最良の可能性がある。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *マッチング ,  決定問題 ,  *超グラフ
準シソーラス用語： 多項式時間 ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： 完全マッチング ,  吸収法 ,  複雑さ

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

タイトルに関連する用語 (3件)： ハイパーグラフ ,  マッチング ,  複雑さ