文献

J-GLOBAL ID：202102233144775072   整理番号：21A3409198

ランダムグラフにおけるHamiltonサイクルの正方形の三角形回復力【JST・京大機械翻訳】

Triangle resilience of the square of a Hamilton cycle in random graphs

著者 (4件)： Fischer Manuela (Institute of Theoretical Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland) ,  Skoric Nemanja (Institute of Theoretical Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland) ,  Steger Angelika (Institute of Theoretical Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland) ,  Trujic Milos (Institute of Theoretical Computer Science, ETH Zuerich, 8092 Zuerich, Switzerland)
資料名： Journal of Combinatorial Theory. Series B  (Journal of Combinatorial Theory. Series B)
巻： 152  ページ： 171-220  発行年： 2022年 
JST資料番号： E0780A  ISSN： 0095-8956  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 2008年にSudakovとVuによって最初に導入されたので,ランダムグラフにおけるレジリエンス問題の研究は,確率的組合せにおいて多くの注目を受けた。特に興味深いことは,スパニング構造のレジリエンス問題である。多くの三角形を含むスパニング構造に対して,局所レジリエンスは,あらゆる頂点に入射する無視できる量のエッジを除去することによって,構造のすべてのコピーを破壊することから敵対を防止できないことが知られている。本論文では,局所レジリエンスの概念をH-レジリエンスに一般化し,ハミルトンサイクルの正方形の封じ込め問題に対する有用性を実証した。特に,ランダムグラフGnのあらゆる部分グラフGにおいて,p≧Clog3n/n,次にw.h.p.が,Gn,pからその三角形の少なくとも(4/9+o(1))分数に留まるならば,H.h.p.がハミルトンサイクルの二乗が存在するならば,一定のC>0が存在することを示す。定数4/9は最適であり,pの値は,そのような構造の最良既知外観閾値でわずかに改善し,対数因子まで最適であった。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： レジリエンス ,  *部分グラフ ,  対数
準シソーラス用語： *ランダムグラフ , 【Automatic Indexing@JST】

著者キーワード (3件)： 三角形回復力 ,  Hamiltonサイクル ,  ランダムグラフ

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

タイトルに関連する用語 (5件)： ランダムグラフ ,  サイクル ,  正方形 ,  三角形 ,  回復