文献

J-GLOBAL ID：201802238981186297   整理番号：18A0328163

グラフにおける開放近傍位置支配のアルゴリズム的側面【Powered by NICT】

Algorithmic aspects of open neighborhood location-domination in graphs

著者 (2件)： Panda B.S. (Department of Mathematics, Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, India) ,  Pandey Arti (Department of Mathematics, Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, India)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 216  号： P1  ページ： 290-306  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： (i)全てのv∈VのNG(v)∩D≠0,および(ii)異なる全ての頂点対uのNG(u)∩D≠N(v)∩D,v∈VならばグラフG=(V , E)の集合D⊆Vは開放近傍位置決め-支配集合と呼ばれる(OLD)。グラフG=(V , E)が与えられた場合,Min古い集合問題は最小濃度の古い集合を見つけることである。グラフG=(V , E)と正整数kが与えられたとき,決定古い集合問題は,Gが高々kの濃度の古い集合を持つかどうかを決定することである。決定古い集合問題は,一般のグラフに対してNP-完全ことが知られている。本論文において,筆者らは2部グラフ,平面グラフ,スプリットグラフと二重弦グラフのためのNP完全のままであることを示すことにより決定古い集合問題のNP完全性結果を拡張した。決定古い集合問題は有界木幅グラフのための線形時間で解くことができることを証明した。,樹木におけるMin古い集合問題のための線形時間アルゴリズムを提案した。Min古い集合問題のための(2 +3 ln Δ)-近似アルゴリズムを提案し,NP⊆DTIME(VO(log V))なければMin古い集合問題は任意のε>0に対し12(1 ε)ln V以内で近似できないことを示した。最後に,Min古いセット問題である最大次数3の2部グラフのAPX完全なことを証明した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *アルゴリズム ,  *グラフ ,  最小濃度 ,  平面グラフ ,  位置決め ,  線形性
準シソーラス用語： 次数 ,  近似アルゴリズム ,  線形時間アルゴリズム ,  二部グラフ ,  支配集合 ,  *近傍 , 【Automatic Indexing@JST】

著者キーワード (6件)： 支配 ,  弦グラフ ,  グラフアルゴリズム ,  近似アルゴリズム ,  NP完全 ,  APX完全

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

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