A comparison of node‐based and arc‐based hop‐indexed formulations for the Steiner tree problem with hop constraints

DOI10.1002/net.22086MaRDI QIDQ6066244

Pedro Moura, Luís Gouveia, Bernard Fortz

Publication date: 12 December 2023

Published in: Networks (Search for Journal in Brave)

zbMATH Keywords

integer programmingnetwork designlinear programming relaxationSteiner treehop constrainthop-indexed model

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Hop constrained Steiner trees with multiple root nodes
• On the hop-constrained survivable network design problem with reliable edges
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• Multicommodity flow models for spanning trees with hop constraints
• The Steiner tree problem with hop constraints
• Layered graph approaches for combinatorial optimization problems
• Extended formulation for hop constrained distribution network configuration problems
• A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• Hop‐level flow formulation for the survivable network design with hop constraints problem
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs