کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949893 1364262 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graph editing to a fixed target
ترجمه فارسی عنوان
ویرایش گراف به یک مقصد ثابت
کلمات کلیدی
ویرایش گراف، رابطه انعطاف پذیری نمودار، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H-Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP-complete cases depending on the choice of H. Moreover, when G is AT-free, chordal or planar, we show that H-Minor Edit is polynomial-time solvable for all graphs H.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 181-190
نویسندگان
, , ,