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

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

İbrahim Akgün, Barbaros C. Tansel

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 programmingminimum spanning treeMiller-Tucker-Zemlin constraintsdegree-enforcing constraintsflow formulationrooted arborescence

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Mixed integer programming (90C11)

Related Items

Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm ⋮ The generalized dependency constrained spanning tree problem ⋮ Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem ⋮ A strong symmetric formulation for the min-degree constrained minimum spanning tree problem ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ 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 ⋮ A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem ⋮ The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm ⋮ New genetic algorithm approach for the MIN-degree constrained minimum spanning tree ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ A unifying model for locally constrained spanning tree problems ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites Work

• 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
• A branch and cut method for the degree-constrained minimum spanning tree problem
• 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