کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950884 | 1441038 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Packing plane spanning trees and paths in complete geometric graphs
ترجمه فارسی عنوان
بسته بندی هواپیما در درختان و مسیرها در نمودارهای هندسی کامل قرار دارد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات ترکیبی نمودار هندسی، درخت پوشا، نمودارهای لبه مجزا،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph GKn on any set S of n points in general position in the plane? We show that this number is in Ω(n). Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 124, August 2017, Pages 35-41
Journal: Information Processing Letters - Volume 124, August 2017, Pages 35-41
نویسندگان
Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc van Kreveld, Maarten Löffler, Alexander Pilz, Bettina Speckmann, Emo Welzl,