New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints

DOI10.1016/j.ejor.2011.01.051zbMath1252.90085OpenAlexW1984620595MaRDI QIDQ421519

İbrahim Akgün, Barbaros C. Tansel

Publication date: 14 May 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2011.01.051

zbMATH Keywords

integer programminggraph theoryspanning treeshop constraintsMiller-Tucker-Zemlin constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items (7)

Lower and upper bounds for the spanning tree with minimum branch vertices ⋮ An exact approach for the minimum-cost bounded-error calibration tree problem ⋮ Two dependency constrained spanning tree problems ⋮ Minimum weight clustered dominating tree problem ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ Relations, models and a memetic approach for three degree-dependent spanning tree problems ⋮ The hop-constrained minimum cost flow spanning tree problem with nonlinear costs: an ant colony optimization approach

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• Multicommodity flow models for spanning trees with hop constraints
• The 2-hop spanning tree problem
• The traveling salesman problem and its variations
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• New formulations and solution procedures for the hop constrained network design problem.
• 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
• Modeling and solving the rooted distance-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
• Using a Hop-Constrained Model to Generate Alternative Communication Network Design
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Packet Routing in Telecommunication Networks with Path and Flow Restrictions
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Design of Survivable Networks: A survey
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Steiner tree problems

This page was built for publication: New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints