Solving the minimum label spanning tree problem by mathematical programming techniques

DOI10.1155/2011/143732zbMath1236.90134OpenAlexW2001366300WikidataQ58655016 ScholiaQ58655016MaRDI QIDQ666399

Andreas M. Chwatal, Günther R. Raidl

Publication date: 8 March 2012

Published in: Advances in Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2011/143732

zbMATH Keywords

minimum label spanning tree problemodd-hole inequalities

Mathematics Subject Classification ID

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

Related Items (6)

Complexity and approximation results on the shared transportation problem ⋮ Finding minimum label spanning trees using cross‐entropy method ⋮ A hybrid metaheuristic for the minimum labeling spanning tree problem ⋮ An improved flow-based formulation and reduction principles for the minimum connectivity inference problem ⋮ Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles ⋮ A polyhedral approach to the generalized minimum labeling spanning tree problem

Uses Software

• SCIP
• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Solving a \(k\)-node minimum label spanning arborescence problem to compress fingerprint templates
• A mixed integer linear formulation for the minimum label spanning tree problem
• Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem
• On the 0,1 facets of the set covering polytope
• On implementing the push-relabel method for the maximum flow problem
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• A note on the minimum label spanning tree.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• Variable neighbourhood search for the minimum labelling Steiner tree problem
• Integer Programming Formulation of Traveling Salesman Problems
• Solving matching problems with linear programming
• Obtaining optimal k -cardinality trees fast

This page was built for publication: Solving the minimum label spanning tree problem by mathematical programming techniques