کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950884 1441038 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Packing plane spanning trees and paths in complete geometric graphs
ترجمه فارسی عنوان
بسته بندی هواپیما در درختان و مسیرها در نمودارهای هندسی کامل قرار دارد
کلمات کلیدی
مشکلات ترکیبی نمودار هندسی، درخت پوشا، نمودارهای لبه مجزا،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , , , , , ,