文章基本信息

标题：The degree constrained k-cardinality minimum spanning tree problem: a lexi-search algorithm
本地全文：下载
作者：Kumar, T. ; Purusotham, S.
期刊名称：Decision Science Letters
印刷版ISSN：1929-5804
电子版ISSN：1929-5812
出版年度：2018
卷号：7
期号：3
页码：301-310
DOI：10.5267/j.dsl.2017.7.002
语种：English
出版社：Growing Science Publishing Company
摘要：This paper deals with the degree constrained k-cardinality minimum spanning tree (k-MSTPD) problem defined on a connected, edge weighted and undirected graph. The aim of this problem is to determine the least weighted spanning tree with exactly k vertices such that except the root vertex, no other vertex in the resultant spanning tree exceeds the specified degree limit. The k-MSTPD problem has many practical applications for the design of electric, communication, and transportation networks. The problem is then formulated as a zero-one programming. In this paper, an exact algorithm known as Lexi-search algorithm (LSA) is developed to tackle the k-MSTPD problem. Furthermore, the developed LSA is programmed in Matlab and tested on some benchmark instances as well as on random instances and the respective results are reported. The obtained experimental results showed that the developed LSA takes significantly less time to find the optimal solutions.
关键词：k-cardinality minimum spanning tree;Lexi-search algorithm;Degree constraint