文献

J-GLOBAL ID：202002260240119053   整理番号：20A0148231

グラフにおける二重ローマ支配に関するアルゴリズム的結果【JST・京大機械翻訳】

Algorithmic results on double Roman domination in graphs

著者 (3件)： Banerjee S. (Indian Institute of Technology (ISM), Dhanbad, India) ,  Henning Michael A. (Mathematics of Pure and Applied Mathematics, University of Johannesburg, Auckland Park, South Africa) ,  Pradhan D. (Indian Institute of Technology (ISM), Dhanbad, India)
資料名： Journal of Combinatorial Optimization  (Journal of Combinatorial Optimization)
巻： 39  号： 1  ページ： 90-114  発行年： 2020年 
JST資料番号： W1143A  ISSN： 1382-6905  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフ[数式:原文を参照]を与えると,関数[数式:原文を参照]は,(i)[数式:原文を参照]によるあらゆる[数式:原文を参照]に対して,fの下では2つ,または,[数式:原文を参照]による各頂点vに対しては,少なくとも2つのvがあり,[数式:原文を参照]を伴うvの少なくとも1つの近傍が存在する。二重Roman支配関数fの重みは[数式:原文を参照]である。[数式:原文を参照]によって表されるGの二重Roman支配数は,G上の二重Roman支配関数の最小重みである。グラフ[数式:原文を参照]に対して,Min-Double-RDFは,[数式:原文を参照]による二重Roman支配関数fを見出すことである。Min-Double-RDFの決定版は,コードグラフと二部グラフに対してNP完全であることを示した。本論文において,著者らは最初に,Min二重RDFの決定版が,無方向経路グラフ,コード二部グラフ,および円グラフに対してNP完全であることを示すことにより,Min二重RDFの決定版の既知NP完全性を強化した。次に,適切な区間グラフとブロックグラフにおける二重Roman支配数を計算するための線形時間アルゴリズムを提示した。次に,Min-Double-RDFの近似可能性について議論し,3正則二部グラフにおける2近似アルゴリズムを提示した。Copyright 2019 Springer Science+Business Media, LLC, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 近似法 ,  *アルゴリズム
準シソーラス用語： 近似アルゴリズム ,  線形時間アルゴリズム ,  区間グラフ ,  NP完全性 ,  二部グラフ , 【Automatic Indexing@JST】

著者キーワード (5件)： 支配 ,  ローマの支配 ,  二重ローマ支配 ,  多項式時間アルゴリズム ,  NP完全

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

タイトルに関連する用語 (4件)： グラフ ,  ローマ ,  支配 ,  アルゴリズム