多経路カット問題の準多項式マルチカット模倣ネットワークとカーネル化【JST・京大機械翻訳】

Wahlstrom Magnus

プレプリント

J-GLOBAL ID：202202213359963589 整理番号：21P0024896

多経路カット問題の準多項式マルチカット模倣ネットワークとカーネル化【JST・京大機械翻訳】

Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems

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

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

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

kが端末の全容量であり,多項式時間における準多項式サイズの模倣ネットワークを計算する方法と同様に,非有向グラフにおける端末集合上の最小マルチカットに対するk ̄O(logk)エッジの正確な模倣ネットワークの存在を示す。後者の結果として,いくつかの問題は,Edge Multiway Cut,任意のグループに対するグループフィードバックEdge Set,および解とカット要求の数によってパラメータ化されたEdge Multicutを含む準多項式カーネルを持つことを示す。結果は,スパースカットに沿ったグラフの再帰的分解とスパース化によって,s-Multiway Cutのためにカーネルで使用するマトロイドベースの無関係なエッジ方式を結合した。これは,s-Multiway Cutのカーネルがsの一定値(KraschとWahlstr”om,FOCS2012)のために,マルチウェイCut問題のカーネル化に関する最初の進展である。【JST・京大機械翻訳】

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

グラフ理論基礎

, , , , ,

前のページに戻る