Finding minimal branchings with a given number of arcs
DOI:
https://doi.org/10.2298/YJOR0201001CKeywords:
Combinatorial optimization, weighted graphs, minimal branching.Abstract
We describe an algorithm for finding a minimal s-branching (where s is a given number of its arcs) in a weighted digraph with an a symetric weight matrix. The algorithm uses the basic principles of the method (previously developed by J. Edmonds) for determining a minimal branching in the case when the number of its arcs is not specified in advance. Here we give a proof of the correctness for the described algorithm.References
Bellmore, M., and Hong, S., "Transformation of the multisalesman problem to the standard traveling salesman problem", J. Assoc. Comp. Mach., 21 (1974) 501-504.
Bock, F.C., "An algorithm to construct a minimum directed spanning tree in a directed network", in: Developments in Operations Research, B. Avi-Itzak (ed.), Gordon and Breach, New York, 1971, 29-44.
Camerini, M.P., Fratta, L., and Maffioli, F., "A note on finding optimum branching", Networks, 9 (1979) 309-312.
Chu, Y.I., and Lin, T.H., "On the shortest arborescence of a directed graph", Scientia Sinica, 4 (1965) 1396-1400.
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., and Schrijver, A., Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998.
Cvetković, D., "Finding a shortest rooted forest", unpublished report, Faculty of Electrical Engineering, Belgrade, 1987. (in Serbian)
Cvetković, D., and Žangalović, M., "An algorithm for finding minimal branchings", Proceedings of XXIV Yugoslav Symposium in Operations Research, 1997, 183-186.
Cvetković, D., Dimitrijević, V., and Milosavljević, M., Variations on the Traveling Salesman Theme, Libra Produkt, Belgrade, 1996.
Dantzig, G.B., and Ramser, J.H., "The truck dispatching problem", Management Sci., 6 (1960) 80-91.
Edmonds, J., "Optimum branchings", J. Res. Nat. Bur. Standards, B, 71 (1967) 233-240; reprinted in: Mathematics of Decision Sciences, Lectures in Appl. Math., G. Dantzig, A., Vienott (eds.), 1968, 346-351.
Fischetti, M., Hamacher, H., Jørnstensen, K., and Maffioli, F., "Weighted k-cardinality trees: complexity and polyhedral structure", Networks, 24 (1994) 11-21.
Gabow, H.N., Galil, Z., Spencer, T., and Tarjan, R.E., "Efficient algorithms for finding minimum spanning trees in nondirected and directed graphs", Combinatorica, 6 (2) (1986) 109-122.
Karp, R.M., "A simple derivation of Edmonds' algorithm for optimum branchings", Networks, 1 (1972) 265-272.
Lawler, E.L., "Matroid intersection algorithms", Math. Programming, 9 (1975) 31-56.
Minieka, E., Optimization Algorithms for Networks and Graphs, Marcel Dekker Inc., New York-Basel, 1978.
Tarjan, R.E., "Finding optimum branchings", Networks, 7 (1977) 25-35.
Thulasiraman, K., and Swamy, M.N.S., Graphs: Theory and Algorithms, John Wiley & Sons, New York, 1992.
Downloads
Published
Issue
Section
License
Copyright (c) 2002 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
