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

DOI10.1016/J.COR.2009.03.006zbMATH Open1171.90532OpenAlexW2044793578MaRDI QIDQ733522FDOQ733522

Authors: İbrahim Akgün, B. 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

Recommendations

• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• A strong symmetric formulation for the min-degree constrained minimum spanning tree problem
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• Finding min-degree constrained spanning trees faster with a branch-and-cut algorithm
• Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations

zbMATH Keywords

minimum spanning treemixed integer programmingMiller-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)

Cites Work

• Network flows. Theory, algorithms, and applications.
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Title not available (Why is that?)
• An analytical comparison of different formulations of the travelling salesman problem
• Integer Programming Formulation of Traveling Salesman Problems
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Using Lagrangian dual information to generate degree constrained spanning trees
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Title not available (Why is that?)
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Comparison of algorithms for the degree constrained minimum spanning tree
• Edge exchanges in the degree-constrained minimum spanning tree problem

Cited In (17)

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

This page was built for publication: Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints

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