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

DOI10.1007/s11590-013-0665-yzbMath1292.90305OpenAlexW2078274358MaRDI QIDQ2448195

Diego M. B. Silva, Mauricio G. C. Resende, Paola Festa, Geraldo Robson Mateus, Ricardo M. A. Silva, José Fernando Gonçalves

Publication date: 30 April 2014

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: http://repositorio.inesctec.pt/handle/123456789/5403

zbMATH Keywords

heuristicbranch verticesedge swappingconstrained spanning treesminimum branch vertices problemmulti-start heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (8)

An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices ⋮ Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem ⋮ A branch-and-cut algorithm for the minimum branch vertices spanning tree problem ⋮ Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ A genetic approach for the 2‐edge‐connected minimum branch vertices problem ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ Spanning Trees with Few Branch Vertices

Uses Software

• TSPLIB
• MersenneTwister
• NETGEN
• STL

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Lower and upper bounds for the spanning tree with minimum branch vertices
• Bounded-degree spanning tree problems: models and new algorithms
• Negative-cycle detection algorithms
• An SST-based algorithm for the steiner problem in graphs
• A graph coloring algorithm for large scheduling problems
• TSPLIB—A Traveling Salesman Problem Library
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Mersenne twister

This page was built for publication: An edge-swap heuristic for generating spanning trees with minimum number of branch vertices