Solving the optimum communication spanning tree problem

DOI10.1016/J.EJOR.2018.07.055zbMath1403.90214OpenAlexW2885165520WikidataQ129476440 ScholiaQ129476440MaRDI QIDQ1991267

Carlos Luna-Mota, Elena Fernández, Carlos Armando Zetina, Iván A. Contreras

Publication date: 30 October 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://spectrum.library.concordia.ca/984182/1/Contreras%202018.pdf

zbMATH Keywords

networksnetwork optimizationBenders decompositionspanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Communication networks in operations research (90B18) Deterministic network models in operations research (90B10)

Related Items (3)

Models of random subtrees of a graph ⋮ Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design ⋮ NeuroPrim: an attention-based model for solving NP-hard spanning tree problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Lagrangean bounds for the optimum communication spanning tree problem
• Benders, metric and cutset inequalities for multicommodity capacitated network design
• Tight bounds from a path based formulation for the tree of hub location problem
• Integrated airline scheduling
• Practical enhancements to the Magnanti-Wong method
• The tree of hubs location problem
• Partitioning procedures for solving mixed-variables programming problems
• Optimization, approximation, and complexity classes
• Approximation algorithms for some optimum communication spanning tree problems
• A comparison of optimal methods for local access uncapacitated network design
• Combined column-and-row-generation for the optimal communication spanning tree problem
• Multi-level facility location problems
• A survey on Benders decomposition applied to fixed-charge network design problems
• Representations for genetic and evolutionary algorithms. With a foreword by David E. Goldberg.
• Branching rules revisited
• Algorithms for the optimum communication spanning tree problem
• A Benders Decomposition Approach for the Locomotive and Car Assignment Problem
• Benders Decomposition for Large-Scale Uncapacitated Hub Location
• Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem
• Optimum Communication Spanning Trees
• Acceleration of cutting-plane and column generation algorithms: Applications to network design
• Simultaneous Assignment of Locomotives and Cars to Passenger Trains
• Tailoring Benders decomposition for uncapacitated network design
• Multi-Terminal Network Flows
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• Multicommodity Distribution System Design by Benders Decomposition
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
• A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees
• Exact algorithms for minimum routing cost trees
• Strong formulations for network design problems with connectivity requirements
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• An approach to a problem in network design using genetic algorithms
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• On Optimal Solutions for the Optimal Communication Spanning Tree Problem
• Design of Survivable Networks: A survey
• Investigation of some branch and bound strategies for the solution of mixed integer linear programs
• On Hamiltonian Circuits

This page was built for publication: Solving the optimum communication spanning tree problem