文献

J-GLOBAL ID：201802222815416331   整理番号：18A0328154

近隣Hellyグラフについて【Powered by NICT】

On neighborhood-Helly graphs

著者 (6件)： Groshaus Marina (Departamento de Computacion, Universidad de Buenos Aires, Argentina) ,  Groshaus Marina (Consejo Nacional de Investigaciones Cientificas y Tecnicas, Argentina) ,  Lin Min Chih (Instituto de Calculo and Departamento de Computacion, Universidad de Buenos Aires, Argentina) ,  Lin Min Chih (Consejo Nacional de Investigaciones Cientificas y Tecnicas, Argentina) ,  Szwarcfiter Jayme L. (Inst Matematica, COPPE and NCE, Universidade Federal do Rio de Janeiro, Brazil) ,  Szwarcfiter Jayme L. (Instituto Nacional de Metrologia, Qualidade e Tecnologia, Brazil)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 216  号： P1  ページ： 191-202  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： F対のセットが交差する場合,いくつかの集合の部分集合の族Fは交差する。の各交差サブファミリーは,共通の要素を含む場合ファミリーFはH ellyである。本論文では,グラフの頂点近傍のファミリーを調べ,Helly,であるかどうか,またかもそれらは遺伝性Hellyする,すなわちグラフの誘導部分グラフのHellyである決定を目的とした。近傍は全て,または全ての閉じた,あるいは混合した場合,すなわち,いくつかの開放と閉鎖を調べた。混合近傍では,二種類の考慮すべき各頂点の近傍の選択の固定または任意の選択。固定混合近傍により,頂点の近傍のための,開放または閉鎖,選択は,事前に知られていることを意味する,入力の一部である。一方,任意の選択は,選択プロセスに沿って作ることができることを意味している。オープン,クローズおよび固定混合近傍の場合,キャラクタリゼーション,Hellyと遺伝性Hellyに近隣の両方を記述した。特性化した二種類の拡張の概念に基づいて,または,遺伝性の場合,禁止誘導部分グラフ。多項式時間認識アルゴリズムはキャラクタリゼーションから直接的に従った。とは対照的に,任意の混合近傍のための,近隣のファミリーは,Hellyまたは遺伝性Hellyであるかどうかを決定するNP完全であることを証明した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *グラフ ,  キャラクタリゼーション ,  部分グラフ ,  遺伝 ,  部分集合
準シソーラス用語： 認識アルゴリズム ,  多項式時間 ,  近傍 , 【Automatic Indexing@JST】

著者キーワード (4件)： 複雑性 ,  拡張 ,  Helly特性 ,  NP hardness

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

タイトルに関連する用語 (1件)： グラフ