文献

J-GLOBAL ID：202002233874996909   整理番号：20A1201407

Hフリー弦グラフのいくつかのクラスのための効率的な支配について【JST・京大機械翻訳】

On efficient domination for some classes of H-free chordal graphs

著者 (2件)： Brandstaedt Andreas (Institut fuer Informatik, Universitaet Rostock, D-18051 Rostock, Germany) ,  Mosca Raffaele (Dipartimento di Economia, Universita degli Studi “G. D’Annunzio”, Pescara 65121, Italy)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 281  ページ： 81-95  発行年： 2020年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 有限無有向グラフグラフGにおける頂点集合Dは,Gのあらゆる頂点が正確にDの頂点により支配されるならば,Gの効率的な支配集合(短い場合)である。GにおけるE.D.S.の存在を求める有効次元(ED)問題は,2P3フリーコードグラフのような非常に限定されたグラフクラスに対してさえNP完全であることが知られているが,P6フリーコードグラフ(P6フリーグラフに対してさえ)の多項式時間において可解である。NP完全Exact Cover問題からの標準的な低減は,EDが分割グラフを一般化するコードグラフの非常に特殊なサブクラスに対してNP完全であることを示した。この減少は,EDがNP完全であることを意味しているが,二重gemフリーのコードグラフに対しては,それはgemフリーのコードグラフに対して線形時間で可解であるが,2P2フリーグラフに対しては線形時間で解ける。Hがネット,拡張されたgem,またはS1,2,3であるとき,(加重)EDがHフリーのコードグラフのために多項式時間で解くことができることを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *有向グラフ ,  線形性
準シソーラス用語： 支配集合 ,  多項式時間 , 【Automatic Indexing@JST】

著者キーワード (8件)： 重み付き効率支配 ,  Hフリー弦グラフ ,  NP完全性 ,  ネットフリー弦グラフ ,  拡張GEMフリー弦グラフ ,  S123フリー弦グラフ ,  多項式時間アルゴリズム ,  クリーク幅

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

タイトルに関連する用語 (4件)： 弦 ,  グラフ ,  クラス ,  支配