کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331397 | 686688 | 2005 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: Information Processing Letters - Volume 94, Issue 2, 30 April 2005, Pages 49-53
نویسندگان
Artur Czumaj, Magnús M. Halldórsson, Andrzej Lingas, Johan Nilsson,