時間グラフにおけるフィードバックエッジ集合【JST・京大機械翻訳】

Haag Roman; Molter Hendrik; Niedermeier Rolf; Renken Malte

プレプリント

J-GLOBAL ID：202202201256037300 整理番号：21P0027873

時間グラフにおけるフィードバックエッジ集合【JST・京大機械翻訳】

Feedback Edge Sets in Temporal Graphs

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

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

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

古典的線形時間可解Feedback Edge Set問題は,(静的,非加重)グラフにおいて全てのサイクルを交差する最小数のエッジの発見に関係する。時間的グラフの設定におけるこの問題に関する最初の研究を提供し,そこでは,エッジが特定の時点でのみ存在する。Feedback Edge Setの4つの自然一般化があり,その全てはNP困難であることが分かった。また,いくつかのパラメータ(解サイズ,寿命およびグラフ頂点の数)に関して,これらの問題の扱いやすさを研究し,いくつかのパラメータ化硬度を得たが,また,固定パラメータ扱い性結果を得た。【JST・京大機械翻訳】

, , ,

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

, , ,

前のページに戻る