A new algorithm for degree-constrained minimum spanning tree based on the reduction technique |
| |
| Authors: | Aibing Ning Liang Ma Xiaohua Xiong |
| |
| Institution: | 1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
2. College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, China |
| |
| Abstract: | The degree-constrained minimum spanning tree (DCMST) is an iVP-hard problem in graph theory. It consists of rinding 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. |
| |
| Keywords: | Degree-constrained minimum spanning tree Reduction algorithm Edge exchange technique Combinatorial optimization |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
