کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331397 686688 2005 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
چکیده انگلیسی
We present a generic scheme for approximating NP-hard problems on graphs of treewidth k=ω(logn). When a tree-decomposition of width ℓ is given, the scheme typically yields an ℓ/logn-approximation factor; otherwise, an extra logk factor is incurred. Our method applies to several basic subgraph and partitioning problems, including the maximum independent set problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 94, Issue 2, 30 April 2005, Pages 49-53
نویسندگان
, , , ,