Spanning trees with variable degree bounds
In this paper, we introduce and study a generalization of the degree constrained minimum spanning tree problem where we may install one of several available transmission systems (each with a different cost value) in each edge. The degree of the endnodes of each edge depends on the system installed o...
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | article |
| Language: | eng |
| Published: |
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10773/13285 |
| Country: | Portugal |
| Oai: | oai:ria.ua.pt:10773/13285 |
| Summary: | In this paper, we introduce and study a generalization of the degree constrained minimum spanning tree problem where we may install one of several available transmission systems (each with a different cost value) in each edge. The degree of the endnodes of each edge depends on the system installed on the edge. We also discuss a particular case that arises in the design of wireless mesh networks (in this variant the degree of the endnodes of each edge depend on the transmission system installed on it as well as on the length of the edge). We propose three classes of models using different sets of variables and compare from a theoretical perspective as well as from a computational point of view, the models and the corresponding linear programming relaxations. The computational results show that some of the proposed models are able to solve to optimality instances with 100 nodes and different scenarios. |
|---|