文献

J-GLOBAL ID：201802250496751491   整理番号：18A0328153

固定標的へのグラフ編集【Powered by NICT】

Graph editing to a fixed target

著者 (3件)： Golovach Petr A. (Department of Informatics, Bergen University, PB 7803, 5020 Bergen, Norway) ,  Paulusma Danieel (School of Engineering and Computing Sciences, Durham University, Science Laboratories, South Road, Durham DH1 3LE, United Kingdom) ,  Stewart Iain (School of Engineering and Computing Sciences, Durham University, Science Laboratories, South Road, Durham DH1 3LE, United Kingdom)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 216  号： P1  ページ： 181-190  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 固定グラフHに対して,H-マイナー編集問題は,グラフGと整数kを入力とし,Gが高々kエッジ収縮,端部欠失とバーテックス欠失を総合してHに修正できるかどうかを問う。バーテックス溶解による置換エッジ収縮はH トポロジー副編集問題となる。各問題に対して,Hの選択に依存して多項式時間可解,NP完全例を示した。さらに,GがAT(アステロイダル三つ組)のない,弦または平面,H マイナー編集である全てのグラフHのための多項式時間可解であることを示した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *編集 ,  位相幾何学 ,  溶解 ,  計算量 ,  *グラフ
準シソーラス用語： 多項式時間 , 【Automatic Indexing@JST】

著者キーワード (3件)： グラフ編集 ,  グラフ格納容器関係 ,  計算の複雑さ

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 固定標的 ,  グラフ ,  編集