Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem

DOI10.1016/J.COR.2015.06.012zbMath1349.90636OpenAlexW2136190246WikidataQ57705358 ScholiaQ57705358MaRDI QIDQ342101

Markus Leitner

Publication date: 17 November 2016

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

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

zbMATH Keywords

integer programmingbranch-and-cuthop-constraintsgeneralized network designlayered graph

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18)

Related Items (10)

Layered graph approaches for combinatorial optimization problems ⋮ Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems ⋮ Branch-and-cut methods for the network design problem with vulnerability constraints ⋮ Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints ⋮ An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances

Uses Software

• SteinLib
• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Hop constrained Steiner trees with multiple root nodes
• Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
• Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem
• An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees
• A tabu search heuristic for the generalized minimum spanning tree problem
• Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem
• Multicommodity flow models for spanning trees with hop constraints
• The capacitated minimal spanning tree problem: An experiment with a hop-indexed model
• The 2-hop spanning tree problem
• On implementing the push-relabel method for the maximum flow problem
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• The two-level diameter constrained spanning tree problem
• A new relaxation method for the generalized minimum spanning tree problem
• Heuristic Search for the Generalized Minimum Spanning Tree Problem
• A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems
• The generalized minimum edge-biconnected network problem: Efficient neighborhood structures for variable neighborhood search
• The Generalized Traveling Salesman Problem: A New Genetic Algorithm Approach
• TSPLIB—A Traveling Salesman Problem Library
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Packet Routing in Telecommunication Networks with Path and Flow Restrictions
• The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm
• Solving Steiner tree problems in graphs to optimality
• On the generalized 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
• On generalized minimum spanning trees

This page was built for publication: Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem