Skip to main content
SpringerLink
Log in

An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper presents a new edge-swap heuristic for generating spanning trees with a minimum number of branch vertices, i.e. vertices of degree greater than two. This problem was introduced in Gargano et al. (Lect Notes Comput Sci 2380:355–365, 2002) and has been called the minimum branch vertices problem by Cerulli et al. (Comput Optim Appl 42:353–370, 2009). The heuristic starts with a random spanning tree and iteratively reduces the number of branch vertices by swapping tree edges with edges not currently in the tree. It can be easily implemented as a multi-start heuristic. We report on extensive computational experiments comparing single-start and multi-start variants on our heuristic with other heuristics previously proposed in the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Beasley, J.E.: An SST-based algorithm for the Steiner problem in graphs. Networks 19, 1–16 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  2. Carrabs, F., Cerulli, R., Gaudioso, M., Gentili, M.: Lower and upper bounds for the spanning tree with minimum branch vertices. Technical Report 3, Department of Mathematics and Computer Science, University of Salerno. Salerno, Italy (2009)

  3. Cerulli, R.: Personal, communication. January (2010)

  4. Cerulli, R., Gentili, M., Iossa, A.: Bounded-degree spanning tree problems: models and new algorithms. Comput. Optim. Appl. 42, 353–370 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  5. Cherkassky, B.V., Goldberg, A.V.: Negative-cycle detection algorithms. Technical Report 96–029NEC Research Institute, Inc., Princeton, NJ (1996)

  6. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  7. Gargano, L., Hell, P., Stacho, L., Vaccaro, U.: Spanning trees with bounded number of branch vertices. In 29th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2380, pp. 355–365. Springer, Berlin (2002)

  8. Klingman, D., Napier, A., Stutz, J.: NETGEN—a program for generating large scale (un)capacitated assignment, transportation, and minimum cost flow network problems. Manage. Sci. 20, 814–821 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  9. Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48–50 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  10. Leighton, F.T.: A graph colouring algorithm for large scheduling problems. J. Res. Natl. Bureau Standards. 84(6), 489–503 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  11. Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998)

    Article  MATH  Google Scholar 

  12. Plauger, P.J., Lee, M., Musser, D., Stepanov, A.A.: C++ Standard Template Library. Prentice Hall PTR, Englewood Cliffs (2000)

    Google Scholar 

  13. Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)

    Article  MATH  Google Scholar 

  14. Reinelt, G.: TSPLIB 95 documentation. University of Heidelberg, Technical report (1995)

  15. Silva, D.M.: Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices branch. Master’s thesis, U. Federal de Minas Gerais, Belo Horizonte (MG). Brazil (2011)

Download references

Acknowledgments

The research of R.M.A Silva was partially done while he was a post-doc scholar at AT&T Labs Research in Florham Park, New Jersey, and was partially supported by the Brazilian National Council for Scientific and Technological Development (CNPq), the Foundation for Support of Research of the State of Minas Gerais, Brazil (FAPEMIG), Coordination for the Improvement of Higher Education Personnel, Brazil (CAPES), and Foundation for the Support of Development of the Federal University of Pernambuco, Brazil (FADE). José F. Gonçalves was supported by funds granted by the ERDF through the Programme COMPETE and by the Portuguese Government through FCT – Foundation for Science and Technology, project PTDC/EGE-GES/117692/2010. Diego M. Silva was partially supported by CAPES-MINTER Program between the Federal Universities of Minas Gerais and Lavras, Brazil.

Author information

Authors and Affiliations

  1. Center of Informatics, Federal University of Pernambuco, Av. Jornalista Anibal Fernandes, s/n, Cidade Universitária, CEP 50.740-560 , Recife, PE, Brazil

    Ricardo M. A. Silva

  2. Department of Computer Science, Federal University of Lavras, CEP 37200-000 , Lavras, MG, Brazil

    Diego M. Silva

  3. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA

    Mauricio G. C. Resende

  4. Department of Computer Science, Federal University of Minas Gerais, CEP 31270-010 , Belo Horizonte, MG, Brazil

    Geraldo R. Mateus

  5. LIAAD, Faculdade de Economia do Porto, Universidade do Porto, Rua Dr. Roberto Frias, s/n, 4200-464 , Porto, Portugal

    José F. Gonçalves

  6. Department of Mathematics and Applications “R. Caccioppoli”, University of Napoli FEDERICO II, Compl., MSA, Via Cintia, 80126 , Naples, Italy

    Paola Festa

Authors
  1. Ricardo M. A. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diego M. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mauricio G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Geraldo R. Mateus
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. José F. Gonçalves
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Paola Festa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mauricio G. C. Resende.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Silva, R.M.A., Silva, D.M., Resende, M.G.C. et al. An edge-swap heuristic for generating spanning trees with minimum number of branch vertices. Optim Lett 8, 1225–1243 (2014). https://doi.org/10.1007/s11590-013-0665-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-013-0665-y

Keywords

Search

Navigation