A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems

DOI10.1007/978-3-642-20807-2_30zbMath1341.68008OpenAlexW2256142104MaRDI QIDQ3009777

Günther R. Raidl, Mario Ruthmair

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20807-2_30

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Layered graph approaches for combinatorial optimization problems ⋮ Branch-and-cut methods for the network design problem with vulnerability constraints ⋮ Load-dependent and precedence-based models for pickup and delivery problems ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ Distance Transformation for Network Design Problems

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Modeling and solving the rooted distance-constrained minimum spanning tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An Exact Algorithm for the Steiner Tree Problem with Delays
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Solving Steiner tree problems in graphs to optimality
• Cost-minimal trees in directed acyclic graphs
• The steiner problem in graphs
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs