کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436653 690021 2007 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
NP-hard graph problems and boundary classes of graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
NP-hard graph problems and boundary classes of graphs
چکیده انگلیسی

Any graph problem, which is NP-hard in general graphs, becomes polynomial-time solvable when restricted to graphs in special classes. When does a difficult problem become easy? To answer this question we study the notion of boundary classes. In the present paper we define this notion in its most general form, describe several approaches to identify boundary classes and apply them to various graph problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 389, Issues 1–2, 10 December 2007, Pages 219-236