フォールトトレラントフィードバック頂点集合について【JST・京大機械翻訳】

Misra Pranabendu

プレプリント

J-GLOBAL ID：202202202684458864 整理番号：22P0190418

フォールトトレラントフィードバック頂点集合について【JST・京大機械翻訳】

On Fault Tolerant Feedback Vertex Set

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

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

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

様々なネットワーク設計問題に対するフォールトトレラントデータ構造の研究は,コンピュータ科学における研究の顕著な領域である。同様に,NP-Complete問題の研究は,コンピュータ科学の心臓にあり,アルゴリズムや複雑性に多数の結果をもたらす。本論文では,NP-Complete問題に対するフォールトトレラント解の計算の問題を提起した。それは,いくつかの構成要素の「故障」を生存できる解を計算する。この概念は,ネットワーク信頼性,カーネル化(インスタンス圧縮),近似アルゴリズムなどを推定するような様々な理論的および実用的な設定で現れた。本論文では,更なる研究のためにこれらの疑問を強調することを試みた。コンクリート例として,古典的フィードバックVertex Set(FVS)問題のフォールトトレラントバージョンを研究し,フォールトトレラントフィードバックVertex Set(FT-FVS)と呼ぶ。FVSにおいて,入力はグラフGであり,目的は,G-Sが森林であるような頂点Sの最小部分集合を計算することである。FT-FVSにおいて,目的は,G-(S≡v})が任意のv∈V(G)の森林であるような頂点の最小部分集合Sを計算することである。ここで,頂点vは単一頂点故障を示す。この問題はNP-Completeであり,次に,解サイズによってパラメータ化されたFPTアルゴリズムと同様に,一定因子近似アルゴリズムを提示する。様々なNP-Complete問題に対するフォールトトレラント解の計算の問題は将来の研究にとって興味深い方向であると信じる。【JST・京大機械翻訳】

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

システム設計・解析

前のページに戻る