A branch‐and‐cut algorithm for the ring spur assignment problem

DOI10.1002/net.21495zbMath1269.68027OpenAlexW2076448349MaRDI QIDQ5326781

Seán McGarraghy, Paula Carroll, Martine Labbé, Bernard Fortz

Publication date: 6 August 2013

Published in: Networks (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10197/9428

zbMATH Keywords

branch-and-cut algorithmsurvivable network designIP formulationNP-hardness proof

Mathematics Subject Classification ID

Integer programming (90C10) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Models for a Steiner multi-ring network design problem with revenues ⋮ The ring spur assignment problem: new formulation, valid inequalities and a branch-and-cut approach ⋮ Min–max optimization of node‐targeted attacks in service networks

Uses Software

• SONET

Cites Work

• Unnamed Item
• A heuristic procedure for the capacitated \(m\)-ring-star problem
• SONET/SDH ring assignment with capacity constraints
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• Two-connected networks with rings of bounded cardinality
• Polyhedral results for two-connected networks with bounded rings
• On the asymmetric representatives formulation for the vertex coloring problem
• A Branch-and-Cut-and-Price Approach for the Capacitated m-Ring-Star Problem
• Improved Formulations for the Ring Spur Assignment Problem
• The Capacitated m-Ring-Star Problem
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Generalized Subtour Elimination Constraints and Connectivity Constraints
• A simple min-cut algorithm
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• Solving the Two-Connected Network with Bounded Meshes Problem
• Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: A branch‐and‐cut algorithm for the ring spur assignment problem