کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420474 683945 2009 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the complexity of some subgraph problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the complexity of some subgraph problems
چکیده انگلیسی

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NPNP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3531–3539
نویسندگان
, ,