ユニークな二分完全マッチングの代数的表現【JST・京大機械翻訳】

Beniamini Gal

プレプリント

J-GLOBAL ID：202202211804791103 整理番号：22P0297721

ユニークな二分完全マッチングの代数的表現【JST・京大機械翻訳】

Algebraic Representations of Unique Bipartite Perfect Matching

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

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

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

著者らは,実物上の多重線形多項式を用いて,独特のBipartite Perfect Matching関数とBoole Doubleの完全なキャラクタリゼーションを得た。以前の結果に基づいて,著者らは,驚くべきことに,二重記述がスパースであり,Θ(nlogn)において低いl_1ノルムのみ指数を持ち,この結果がマッチング関連関数の他のファミリーにも拡張することを示した。提案アプローチはマッチング被覆格子におけるM「obius数」に依存し,著者らの証明における重要成分はM「obius」反転公式である。これらの多項式表現は複雑性理論結果をもたらす。例えば,ユニークな二部マッチングが古典的決定木に対して回避され,一般化クエリモデルに対してさえもほとんど回避されることを示した。また,関連する2パーティ通信タスクのログランクに結合したタイトなΘ(nlogn)を得た。【JST・京大機械翻訳】

, , , , , , , ,
, 【Automatic Indexing@JST】

計算理論 , グラフ理論基礎

前のページに戻る