無向非重み付き平面グラフにおける最大流活力【JST・京大機械翻訳】

Ausiello Giorgio; Franciosa Paolo G.; Lari Isabella; Ribichini Andrea

プレプリント

J-GLOBAL ID：202202215454267983 整理番号：21P0059090

無向非重み付き平面グラフにおける最大流活力【JST・京大機械翻訳】

Max-flow vitality in undirected unweighted planar graphs

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

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

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

平面非指向性非加重グラフにおけるエッジ集合を決定する高速アルゴリズムを示し,その削除は2つの固定頂点間の最大流れを低減する。これは,一般的無向グラフとst-平面グラフに対して効率的に解かれた最大流動活力問題の特殊ケースである。2つの固定頂点sとtの間の最大流れに関するグラフのエッジの活力を,そのエッジの除去によって引き起こされる最大流れの減少として定義した。本論文では,n頂点を有する平面非指向性非加重グラフにおいてゼロより大きい活力を持つエッジの集合を,O(nlogn)最悪ケース時間およびO(n)空間において見つけることができることを示した。【JST・京大機械翻訳】

, , ,

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

前のページに戻る