Solving the minimum label spanning tree problem by mathematical programming techniques

DOI10.1155/2011/143732MaRDI QIDQ666399zbMATH OpenOpenAlexWikidataFDO

Authors Andreas M. Chwatal, Günther R. Raidl

Publication date 8 March 2012

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

Copyright license Creative Commons Attribution 4.0 International

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) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)

Recommendations

• A mixed integer linear formulation for the minimum label spanning tree problem
• A polyhedral approach to the generalized minimum labeling spanning tree problem
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• An efficient mixed integer linear programming model for the minimum spanning tree problem

Cites work

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

Cited in

(10)

• A polyhedral approach to the generalized minimum labeling spanning tree problem
• Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
• An efficient mixed integer linear programming model for the minimum spanning tree problem
• On the shared transportation problem: computational hardness and exact approach
• Finding minimum label spanning trees using cross‐entropy method
• Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
• An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
• A hybrid metaheuristic for the minimum labeling spanning tree problem
• Complexity and approximation results on the shared transportation problem
• A mixed integer linear formulation for the minimum label spanning tree problem

Describes a project that uses

Uses Software

• SCIP
• CPLEX

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q666399)