کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876077 | 689682 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On minimum average stretch spanning trees in polygonal 2-trees
ترجمه فارسی عنوان
در حداقل ارتفاع درختان چند ضلعی 2 درختان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداقل دراز درختان دراز کششی، حداقل پایه چرخه پایه، چند ضلعی 2 درخت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. For a polygonal 2-tree on n vertices, we present an algorithm to compute a minimum average stretch spanning tree in O(nlogâ¡n) time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees. We show that there is a unique minimum cycle basis in a polygonal 2-tree and it can be computed in linear time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 575, 13 April 2015, Pages 56-70
Journal: Theoretical Computer Science - Volume 575, 13 April 2015, Pages 56-70
نویسندگان
N.S. Narayanaswamy, G. Ramakrishna,