New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints

DOI10.1016/J.COR.2010.05.003zbMATH Open1231.90363OpenAlexW1965140713MaRDI QIDQ709141FDOQ709141

İbrahim Akgün

Publication date: 15 October 2010

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

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

Recommendations

• New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• On formulations and methods for the hop-constrained minimum spanning tree problem
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs

zbMATH Keywords

spanning treesnetwork flowsinteger programminghop constraintsMiller-Tucker-Zemlin constraints

Mathematics Subject Classification ID

Applications of graph theory (05C90) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Title not available (Why is that?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• An analytical comparison of different formulations of the travelling salesman problem
• Integer Programming Formulation of Traveling Salesman Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• Title not available (Why is that?)
• Design of Survivable Networks: A survey
• The Steiner tree problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Modeling and solving the rooted distance-constrained minimum spanning tree problem
• Title not available (Why is that?)
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• Title not available (Why is that?)
• On formulations and methods for the hop-constrained minimum spanning tree problem
• 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
• 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
• Multicommodity flow models for spanning trees with hop constraints
• 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
• The 2-hop spanning tree problem
• Packet Routing in Telecommunication Networks with Path and Flow Restrictions
• New formulations and solution procedures for the hop constrained network design problem.
• Title not available (Why is that?)

Cited In (7)

• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Title not available (Why is that?)
• On formulations and methods for the hop-constrained minimum spanning tree problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• On solving bi-objective constrained minimum spanning tree problems
• Finding bounded diameter minimum spanning tree in general graphs
• Breakout local search for the Steiner tree problem with revenue, budget and hop constraints

This page was built for publication: New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints

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