Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints

DOI10.1016/j.cor.2009.03.006zbMath1171.90532MaRDI QIDQ733522

Barbaros C. Tansel, İbrahim Akgün

Publication date: 16 October 2009

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

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

zbMATH Keywords

mixed integer programming; minimum spanning tree; Miller-Tucker-Zemlin constraints; degree-enforcing constraints; flow formulation; rooted arborescence

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C80: Random graphs (graph-theoretic aspects)

90C11: Mixed integer programming

Related Items

Lower and upper bounds for the spanning tree with minimum branch vertices, New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints, New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints, Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Edge exchanges in the degree-constrained minimum spanning tree problem
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• An analytical comparison of different formulations of the travelling salesman problem
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Using Lagrangian dual information to generate degree constrained spanning trees
• Integer Programming Formulation of Traveling Salesman Problems
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Comparison of algorithms for the degree constrained minimum spanning tree