کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1549106 | 997772 | 2008 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new algorithm for degree-constrained minimum spanning tree based on the reduction technique
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی مواد
مواد الکترونیکی، نوری و مغناطیسی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been preprocessed by reduction algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Progress in Natural Science - Volume 18, Issue 4, 10 April 2008, Pages 495–499
Journal: Progress in Natural Science - Volume 18, Issue 4, 10 April 2008, Pages 495–499
نویسندگان
Aibing Ning, Liang Ma, Xiaohua Xiong,