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., Hong, S. (1974) Transformation of multisalesmen problem to the standard traveling salesman problem. Journal of the Association for Computing Machinery, 21, 500-504
Bock, F.C. (1971) An algorithm to construct a minimum directed spanning tree in a directed network. u: Avi-Itzak B. [ur.] Developments in Operations Research, New York, itd: Gordon and Breach, 29-44
Camerini, M.P., Fratta, L., Maffioli, F. (1979) A note on finding optimum branchings. Networks, 9, 4, 309-312
Chu, Y.I., Lin, T.H. (1965) On the shortest arborescence of a directed graph. Scientia Sinica, China, 4, 1396-1400
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A. (1998) Combinatorial optimization. New York, itd: Wiley
Cvetković, D.M. (1987) Finding a shortest rooted forest. Beograd: Elektrotehnički fakultet, neobjavljeni rukopis
Cvetković, D.M., Čangalović, M.M. (1997) An algorithm for finding minimal branchings. u: Proceedings of XXIV Yugoslav Symposium in Operations Research, 183-186
Cvetković, D.M., Dimitrijević, V., Milosavljević, M.M. (1996) Variations on the travelling salesman theme. Beograd: Libra Produkt
Dantzing, G.B., Ramser, J.H. (1960) The truck dispatching problem. Management Science, 6, 80-91
Edmonds, J. (1967) Optimum branchings. J Res. Nat. Bur. Standards, 71B, 233-240
Fischetti, M., Hamacher, H., Jornsten, K., Maffioli, F. (1994) Weighted $k$-cardinality trees: Complexity and polyhedral structure. Networks, 24, 1, 11-21
Gabow, H.N., Galil, Z., Spencer, T., Tarjan, R.E. (1986) Efficient algorithms for finding minimum spanning trees in nondirected and directed graphs. Combinatorica, 6, (2), 109-122
Karp, R.M. (1972) A simple derivation of Edmonds' algorithm for optimum branching. Networks, 1, 265-272
Lawler, E.L. (1975) Matroid intersection algorithms. Mathematical Programming Series A, 9, 1, 31-56
Minieka, E. (1978) Optimization algorithms for networks and graphs. New York-Basel: Marcel Dekker
Tarjan, R.E. (1977) Finding optimum branchings. Networks, 7, 1, 25-35
Thulasiraman, K., Swamy, M.N.S. (1992) Graphs: Theory and algorithms. New York, itd: Wiley
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
