Degree-constrained minimum spanning tree |
| |
Authors: | Subhash C Narula |
| |
Affiliation: | Rensselaer Polytechnic Institute, Troy, NY 12181, U.S.A.;Universidad Nacional Technica de Piora, Peru |
| |
Abstract: | In this paper the problem of a degree-constrained minimum spanning tree (DCMST) is defined. The problem is formulated as a linear 0–1 integer programming problem. A primal and a dual heuristic (construction) procedure and a branch-and-bound algorithm are proposed to construct a DCMST. These procedures are illustrated with a simple example. Some computational experience with these algorithms is also reported. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|