کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328488 | 684038 | 2005 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tree decompositions with small cost
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The f-cost of a tree decomposition ({Xi|iâI},T=(I,F)) for a function f:NâR+ is defined as âiâIf(|Xi|). This measure associates with the running time or memory use of some algorithms that use the tree decomposition. In this paper, we investigate the problem to find tree decompositions of minimum f-cost. A function f:NâR+ is fast, if for every iâN: f(i+1)⩾2f(i). We show that for fast functions f, every graph G has a tree decomposition of minimum f-cost that corresponds to a minimal triangulation of G; if f is not fast, this does not hold. We give polynomial time algorithms for the problem, assuming f is a fast function, for graphs that have a polynomial number of minimal separators, for graphs of treewidth at most two, and for cographs, and show that the problem is NP-hard for bipartite graphs and for cobipartite graphs. We also discuss results for a weighted variant of the problem derived of an application from probabilistic networks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 145, Issue 2, 15 January 2005, Pages 143-154
Journal: Discrete Applied Mathematics - Volume 145, Issue 2, 15 January 2005, Pages 143-154
نویسندگان
Hans L. Bodlaender, Fedor V. Fomin,