分割マトロイドにおける塩基対の交換距離【JST・京大機械翻訳】

Berczi Kristof; Schwarcz Tamas

プレプリント

J-GLOBAL ID：202202215224119713 整理番号：22P0298429

分割マトロイドにおける塩基対の交換距離【JST・京大機械翻訳】

Exchange distance of basis pairs in split matroids

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

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

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

基底交換原理は,マトロイド理論の開発における駆動力であった。しかしながら,アキシムは,さらなる進展に対する主要なスタンブリングブロックである塩基の関係の局所的特性化のみを与え,マトロイド基底の構造に関するグローバルな理解を提供することは,マトロイド最適化における基本的目標である。対称交換の構造を研究する間,Gabowは,どんな塩基対が対称交換のシーケンスを許すという問題を提起した。交換アキシムの異なった拡張をホワイトによって提案して,それは互換性のある基底シーケンスの等価性を調査した。これらの予測は,マトロイドの塩基のファミリーが,著者らが認識するよりも,はるかに強い構造特性を有することを示唆する。本論文では,対称交換の観点からマトロイドの基底ペアの距離を研究した。特に,著者らは,熱帯幾何学の観点からマトロイドポリトープの研究によって動機づけられたクラスである分割マトロイドに対して,基底ペアを別のものに変換する最短可能な交換シーケンスを決定する多項式時間アルゴリズムを与えた。共ロールとして,この大規模クラスに対する上記の長年の予想を検証した。分割マトロイドのサブクラスとして,結果は,同様に,舗装マトロイドのための予想を解決した。【JST・京大機械翻訳】

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

グラフ理論基礎

前のページに戻る