矛盾のないハイパーグラフマッチング【JST・京大機械翻訳】

Glock Stefan; Joos Felix; Kim Jaehoon; Kuehn Marcus; Lichev Lyuben

プレプリント

J-GLOBAL ID：202202207781156416 整理番号：22P0348651

矛盾のないハイパーグラフマッチング【JST・京大機械翻訳】

Conflict-free hypergraph matchings

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2022年05月11日プレプリントサーバーでの情報更新日： 2022年05月11日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

PippengerとFranklとR「odl状態」の精巧な定理は,小さな最大共度を持つ,ほとんど完全なマッチングを持つ,ほぼ規則的で均一な超グラフHが,ほとんど完全なマッチングを持つ。この結果を,矛盾が部分集合C≡E(H)の収集Cを介して符号化される,ΔΨconflictフリーのマッチングを得ることによって拡張した。著者らは,Mが部分集合としてCの要素を含んでいないならば,マッチングM⊆E(H)が無矛盾であることを示した。Cに関する自然仮定の下で,著者らはHが無矛盾で,ほとんど完全なマッチングを有することを証明した。これは多くの応用を持ち,その1つがいわゆる「高高gのSteinerシステムに対して新しい漸近結果をもたらす。著者らの主なツールは,著者らは,「conのないマッチングプロセスと呼ぶランダム greedy欲アルゴリズムであった。【JST・京大機械翻訳】

, , , ,
, 【Automatic Indexing@JST】

グラフ理論基礎

前のページに戻る