×

Minimal spanning trees with a constraint on the number of leaves. (English) Zbl 0957.90010

Summary: We discuss minimal spanning trees with a constraint on the number of leaves. Tree topologies appear when designing centralized networks. The constraint on the number of leaves arises because the software and hardware associated to each terminal differs accordingly with its position in the tree. Usually, the software and hardware associated to a “degree-1” terminal is cheaper than the software and hardware used in the remaining terminals because for any intermediate terminal \(j\) one needs to check if the arrival message is destined to that node or to any other node located after node \(j\). As a consequence, that particular terminal needs software and hardware for message routing. On the other hand, such equipment is not needed in “degree-1” terminals. Assuming that the hardware and software for message routing in the nodes is already available, the above discussion motivates a constraint stating that a tree solution has to contain exactly a certain number of “degree-1” terminals. We present two different formulations for this problem and some lower bounding schemes derived from them. We discuss a simple local-exchange heuristic and present computational results taken from a set of complete graphs with up to 40 nodes. Integer Linear Programming formulations for related problems are also discussed at the end.

MSC:

90B10 Deterministic network models in operations research
90C10 Integer programming
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Edmonds, J., Optimum branchings in mathematics of the decision sciences, (Dantzig, G. B.; Veinott, A. F., Lectures in Applied Mathematics (1968)), 346
[2] Fernandes, M. L., O problema da árvore de suporte de custo mínimo com uma restrição adicional no número de folhas, (Master Thesis (1994), Faculdade de Ciências da Universidade de Lisboa), March 1994
[3] Fischetti, M.; Toth, P., An efficient algorithm for the min-sum arborescence problem on complete digraphs, ORSA Journal on Computing, 5, 426-434 (1993) · Zbl 0789.90082
[4] Galbiati, G.; Maffioli, F.; Morzenti, A., A short note on the approximability of the maximum leaves spanning tree problem, Information Processing Letters, 52, 45-49 (1994) · Zbl 0942.68647
[5] Garey, M.; Johnson, D., Computers and Intractability (1979), Freeman and Co
[6] Gavish, B., Topological design of centralized computer networks: Formulations and algorithms, Networks, 12, 355-377 (1982) · Zbl 0493.94021
[7] Gavish, B., Augmented Lagrangean based algorithms for centralized network design, IEEE Trans. on Comm., Com-33, 1247-1257 (1985)
[8] Geoffrion, A. M., Lagrangean relaxation for integer programming, Mathematical Programming Study, 2, 82-114 (1976) · Zbl 0395.90056
[9] Gouveia, L., A 2n-constraint formulation for the capacitated minimal spanning tree problem, Operations Research, 43, 130-141 (1995) · Zbl 0830.90049
[10] Gouveia, L., Multicommodity flow models for spanning trees with Hop constraints, European Journal of Operations Research, 95, 178-190 (1996) · Zbl 0947.90513
[11] Held, M.; Wolfe, P.; Crowder, H., Validation of subgradient optimization, Mathematical Programming, 6, 62-66 (1974) · Zbl 0284.90057
[12] Lu, H.-I.; Ravi, R., The power of local optimization: Approximation algorithms for maximum-leaf spanning tree, (Proc. Allerton Conf. (1992)), 533-542
[13] Prim, R., Shortest connection networks and some generalization, Bell Syst. Tech Journal, 36, 1389-1401 (1957)
[14] Volgenant, A., A Lagrangean approach to the degree-constrained minimum spanning tree problem, European Journal of Operational Research, 39, 325-331 (1989) · Zbl 0674.90071
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.