A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

DOI10.1016/j.cor.2011.01.011zbMath1210.90167OpenAlexW2089581733MaRDI QIDQ716345

Frédéric Semet, Nicolas Jozefowiez, Gilbert Laporte

Publication date: 28 April 2011

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.01.011

zbMATH Keywords

traveling salesman problembranch-and-cutminimum labeling problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Two heuristics for the rainbow spanning forest problem ⋮ On the complexity of rainbow spanning forest problem ⋮ The rainbow spanning forest problem ⋮ A Generic Branch-and-Cut Algorithm for Multiobjective Optimization Problems: Application to the Multilabel Traveling Salesman Problem

Uses Software

• TSPLIB

Cites Work

• An efficient algorithm for the minimum capacity cut problem
• The minimum labeling spanning trees
• On the symmetric travelling salesman problem I: Inequalities
• Heuristic approaches for the Minimum Labelling Hamiltonian Cycle Problem
• The Colorful Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• Some Theorems on Abstract Graphs