文献

J-GLOBAL ID：201802249319240094   整理番号：18A1800496

Dirac閾値以下の超グラフにおけるHamiltonサイクル【JST・京大機械翻訳】

Hamilton cycles in hypergraphs below the Dirac threshold

著者 (2件)： Garbe Frederik (Institute of Mathematics, Czech Academy of Sciences, Zitna 25, 110 00, Prague, Czech Republic) ,  Mycroft Richard (University of Birmingham, Birmingham, B15 2TT, UK)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 133  ページ： 153-210  発行年： 2018年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Hamilton2サイクルを含むn/2に近い最小共次数を持つ4均一ハイパーグラフの正確な特性化を確立した。即時の共ロールとして,4均一ハイパーグラフにおけるHamilton2サイクルに対する正確なDirac閾値を同定した。さらに,著者らの特性化の証明を行うことにより,n/2に近い最小共次数をもつ4均一ハイパーグラフHを与える多項式時間アルゴリズムを提供し,HにおけるHamilton2サイクルを見出すか,そのようなサイクルが存在しないことを証明した。この驚くべき結果はグラフ設定とは対照的であり,Dirac閾値以下ではグラフがハミルトニアンであるかどうかを決定することはNP困難である。k≧3に対するk-一様ハイパーグラフHにおける厳密Hamiltonサイクルも考察し,最小次数δ(H)≧12|V(H)|-O(1)を持つk-均一ハイパーグラフHがタイトHamiltonサイクルを含むかどうかを決定することがNP困難であることを示した。したがって,類似の特性化が,タイトなHamiltonサイクルに対して得られる可能性はない。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： NP困難 ,  キャラクタリゼーション ,  *グラフ ,  *超グラフ ,  ハミルトニアン
準シソーラス用語： 多項式時間アルゴリズム ,  次数 , 【Automatic Indexing@JST】

著者キーワード (2件)： Hamiltonサイクル ,  ハイパーグラフ

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

タイトルに関連する用語 (3件)： 閾値 ,  グラフ ,  サイクル