کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431755 | 688624 | 2006 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A 3-approximation for the pathwidth of Halin graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A 3-approximation for the pathwidth of Halin graphs A 3-approximation for the pathwidth of Halin graphs](/preview/png/431755.png)
چکیده انگلیسی
We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 4, Issue 4, December 2006, Pages 499–510
Journal: Journal of Discrete Algorithms - Volume 4, Issue 4, December 2006, Pages 499–510
نویسندگان
Fedor V. Fomin, Dimitrios M. Thilikos,