کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421002 | 684015 | 2006 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
NP-completeness results for edge modification problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: NP-completeness results for edge modification problems NP-completeness results for edge modification problems](/preview/png/421002.png)
چکیده انگلیسی
The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different areas, and many polynomial-time algorithms and NP-completeness proofs for this kind of problems are known. In this work we prove new NP-completeness results for these problems in some graph classes, such as interval, circular-arc, permutation, circle, bridged, weakly chordal and clique-Helly graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 13, 15 August 2006, Pages 1824–1844
Journal: Discrete Applied Mathematics - Volume 154, Issue 13, 15 August 2006, Pages 1824–1844
نویسندگان
Pablo Burzyn, Flavia Bonomo, Guillermo Durán,