کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420106 | 683895 | 2011 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimization problems in multiple subtree graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study various optimization problems in t-subtree graphs , the intersection graphs of tt-subtrees, where a tt-subtree is the union of tt disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of tt-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 7, 6 April 2011, Pages 588–594
Journal: Discrete Applied Mathematics - Volume 159, Issue 7, 6 April 2011, Pages 588–594
نویسندگان
Danny Hermelin, Dror Rawitz,