کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414725 | 681016 | 2014 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Compatible spanning trees
ترجمه فارسی عنوان
درختان پوشا سازگار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار هندسی، هندسی درخت درختی، نمودار سازگار، درخت های سازگار
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let S be a set of n points in the Euclidean plane in general position and let T be any given plane geometric spanning tree of S . In this work, we study the problem of finding a second plane geometric tree T′T′ spanning S , such that T′T′ is compatible with T and shares the minimum number of edges with T . We prove that there is always a compatible plane geometric tree T′T′ having at most (n−3)/4(n−3)/4 edges in common with T, and that for some plane geometric trees T , any plane tree T′T′ spanning S, compatible with T , has at least (n−2)/5(n−2)/5 edges in common with T.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 5, July 2014, Pages 563–584
Journal: Computational Geometry - Volume 47, Issue 5, July 2014, Pages 563–584
نویسندگان
Alfredo García, Clemens Huemer, Ferran Hurtado, Javier Tejel,