Spanning trees with variable degree bounds. (English) Zbl 1339.90087
Summary: 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.
MSC:
| 90B18 | Communication networks in operations research |
| 90C35 | Programming involving graphs or networks |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Keywords:
OR in telecommunications networks; spanning tree; degree constraints; wireless mesh networksReferences:
| [1] | Almeida, A. M.; Martins, P.; Souza, M. C., Min-degree constrained minimum spanning tree problem: Complexity, properties and formulations, International Transactions in Operational Research, 19, 3, 323-352 (2012) · Zbl 1251.90347 |
| [4] | Caccetta, L.; Hill, S. P., A branch and cut method for the degree-constrained minimum spanning tree problem, Networks, 37, 2, 74-83 (2001) · Zbl 0967.90094 |
| [6] | Cunha, A.; Lucena, A., Lower and upper bounds for the degree-constrained minimum spanning tree problem, Networks, 50, 1, 55-66 (2007) · Zbl 1119.90069 |
| [7] | Duhamel, C.; Gouveia, L.; Moura, P.; Souza, M., Models and heuristics for the k-degree constrained minimum spanning tree problem with node-degree costs, Networks, 60, 1, 1-18 (2012) · Zbl 1251.68169 |
| [8] | Dutta, P.; Jaiswal, S.; Rastogi, R., Villagenet: A low-cost, ieee 802.11-based mesh network for connecting rural areas, Bell Labs Technical Journal, 12, 2, 119-131 (2007) |
| [9] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), W.H. Freeman & Co.: W.H. Freeman & Co. New York, USA · Zbl 0411.68039 |
| [10] | Gouveia, L.; Moura, P., Spanning trees with node degree dependent costs and knapsack reformulations, Electronic Notes in Discrete Mathematics, 36, 985-992 (2010) · Zbl 1274.90310 |
| [11] | Gouveia, L.; Moura, P.; Sousa, A., Prize collecting Steiner trees with node degree dependent costs, Computers & Operations Research, 38, 1, 234-245 (2010) · Zbl 1231.90368 |
| [13] | Knowles, J.; Corne, D.; Oates, M., A new evolutionary approach to the degree constrained minimum spanning tree problem, IEEE Transactions on Evolutionary Computation, 4, 125-134 (2000) |
| [15] | Ljubic, I.; Weiskircher, R.; Pferschy, U.; Klau, G. W.; Mutzel, P.; Fischetti, M., An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Mathematical Programming, 105, 2, 427-449 (2006) · Zbl 1085.90061 |
| [17] | Pejovic, V.; Johnson, D.; Zheleva, M.; Belding, E.; Parks, L.; Stam, G., The bandwidth divide: Obstacles to efficient broadband adoption in rural sub-saharan africa, International Journal of Communication, 6, 2467-2491 (2012) |
| [18] | Raman, B.; Chebrolu, K., Experiences in using WiFi for rural internet in india, IEEE Communications Magazine, 45, 1, 104-110 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
