Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
From MaRDI portal
Publication:5892561
DOI10.1007/s10107-009-0297-2zbMath1218.90201OpenAlexW2100344930MaRDI QIDQ5892561
Luidi Simonetti, Eduardo Uchoa, Luís Gouveia
Publication date: 17 June 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-009-0297-2
Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items (43)
Layered graph approaches for combinatorial optimization problems ⋮ Hop constrained Steiner trees with multiple root nodes ⋮ Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ A new approach for the multiobjective minimum spanning tree ⋮ 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 ⋮ Stabilizing branch‐and‐price for constrained tree problems ⋮ Hop‐level flow formulation for the survivable network design with hop constraints problem ⋮ Extended formulation for hop constrained distribution network configuration problems ⋮ 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 ⋮ Graph fragmentation problem: analysis and synthesis ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem ⋮ A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints ⋮ A polyhedral study of the diameter constrained minimum spanning tree problem ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints ⋮ The time dependent traveling salesman problem: polyhedra and algorithm ⋮ Characterizing acyclic graphs by labeling edges ⋮ 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 ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem ⋮ Natural and extended formulations for the time-dependent traveling salesman problem ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems ⋮ Identification of unidentified equality constraints for integer programming problems ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ Unnamed Item ⋮ A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem ⋮ The hop-constrained minimum cost flow spanning tree problem with nonlinear costs: an ant colony optimization approach ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Layered graphs: applications and algorithms ⋮ Computing a Minimum-Cost k-Hop Steiner Tree in Tree-Like Metrics ⋮ Distance Transformation for Network Design Problems ⋮ Upper and lower bounding procedures for the minimum caterpillar spanning problem ⋮ A New Formulation for Spanning Trees ⋮ An exact method for solving the bi-objective Minimum Diameter-Cost Spanning Tree Problem ⋮ The two-level diameter constrained spanning tree problem ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Design and dimensioning of hydrogen transmission pipeline networks
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees
- The Steiner tree problem
- Multicommodity flow models for spanning trees with hop constraints
- The 2-hop spanning tree problem
- The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
- Notes on polyhedra associated with hop-constrained paths
- Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
- Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
- A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs
- A 2-path approach for odd-diameter-constrained minimum spanning and Steiner trees
- A dual ascent approach for steiner tree problems on a directed graph
- Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem
- Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
- Solving Steiner tree problems in graphs to optimality
- Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
- 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
This page was built for publication: Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
