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

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
نویسندگان
, ,