کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
415709 | 681227 | 2011 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial area bounds for MST embeddings of trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n22)×O(n22)O(2n2)×O(2n2) and the authors conjectured that an improvement below cn×cncn×cn is not possible, for some constant c>0c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 44, Issue 9, November 2011, Pages 529–543
Journal: Computational Geometry - Volume 44, Issue 9, November 2011, Pages 529–543
نویسندگان
Fabrizio Frati, Michael Kaufmann,