文献

J-GLOBAL ID：202002259583705523   整理番号：20A2339468

頂点重み付きグラフにおける安全集合問題の安定な構造 II 認識と複雑さ【JST・京大機械翻訳】

Stable Structure on Safe Set Problems in Vertex-Weighted Graphs II -Recognition and Complexity-

著者 (3件)： Fujita Shinya (School of Data Science, Yokohama City University, Yokohama, Japan) ,  Park Boram (Department of Mathematics, Ajou University, Suwon, Republic of Korea) ,  Sakuma Tadashi (Faculty of Science, Yamagata University, Yamagata, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12301  ページ： 364-375  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Gはグラフであり,letはV(G)に関する非負実値重み関数である。V(G)のあらゆる部分集合Xに対して,Sと[数式:原文を参照]のあらゆる成分Dによって誘発された部分グラフのあらゆる成分Cが,CとDの間にエッジがあるとき,[数式:原文を参照]は,[数式:原文を参照]のあらゆる成分Cのために,(G,w)の加重安全集合である。重み付き安全集合Sによって誘発されたGのサブグラフが接続されたならば,集合Sは(G,w)の連結加重安全集合と呼ばれる。(G,w)の加重安全数[数式:原文を参照]と接続加重安全数[数式:原文を参照]は,すべての加重安全セットと(G,w)のすべての連結加重安全セットの間で,最小重量w(S)である。あらゆる対(G,w)に対して,それらの定義によって[数式:原文を参照]を見ることは容易である。[Journal of Combinatorial Optimization,37:685-701,2019]において,ペア(G,w)が同等性[数式:原文を参照]を満足し,あらゆる加重サイクルが同等性を満たすことを示した。論文の論文では,本論文では,V(G)上の重み関数wごとに[数式:原文を参照]のような接続二部グラフGの完全なリストを与えた。本論文では,コンパニオン論文で発表されているように,筆者らは,このリストにおける任意のグラフGに対して,またV(G)上の重み関数wに対して,(G,w)の最小接続安全集合を計算するためのFPTASが存在することを示す。この結果を証明するために,任意の木TとV(T)の重み関数[数式:原文を参照]に対して,[数式:原文を参照]の最小接続安全集合を計算するFPTASが存在することを証明した。これはBapat et al.[Network,71:82-92,2018]によって提起された質問に完全な答えを与え,EardとRautenbach[Discrete Application Mathematics, 281:216-223,2020]による予想を開示するものである。”.” Ehard and Rautenbach [Discrete Application Mathematics, 281:216-223,2020]。また,グラフが上記のリストにあるかどうか,または線形時間で行わないかどうかを決定する。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  ネットワーク ,  部分グラフ ,  線形性 ,  等価性 ,  *重み関数 ,  複雑性
準シソーラス用語： 二部グラフ , 【Automatic Indexing@JST】

著者キーワード (7件)： 安全な集合 ,  連結安全集合 ,  頂点重み関数 ,  安全な有限 ,  ネットワーク多数決 ,  ネットワーク脆弱性 ,  部分グラフコンポーネント多項式

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 頂点 ,  グラフ ,  集合 ,  問題 ,  複雑さ