An exact algorithm for the capacitated shortest spanning arborescence

DOI10.1007/BF02098285zbMATH Open0844.90104MaRDI QIDQ1908299FDOQ1908299

Authors: Daniele Vigo, Paolo Toth 

Publication date: 18 March 1996

Published in: Annals of Operations Research (Search for Journal in Brave)

Recommendations

• A branch and bound algorithm for the capacitated minimum spanning tree problem
• A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Finding minimum cost directed trees with demands and capacities
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem

zbMATH Keywords

network designroutingbranch-and-boundheuristic algorithmsLagrangian relaxationcapacitated shortest spanning arborescencecomplete and loop-free digraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonlinear systems in control theory (93C10)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• Finding optimum branchings
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Optimum branchings
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• An Exact Algorithm for the Vehicle Routing Problem with Backhauls
• A branch and bound algorithm for the multiple depot vehicle scheduling problem
• Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
• Efficient algorithms for a family of matroid intersection problems
• A Branch-and-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• An exact algorithm for the asymmetrical capacitated vehicle routing problem
• An Additive Bounding Procedure for Combinatorial Optimization Problems
• Title not available (Why is that?)
• A heuristic algorithm for the asymmetric capacitated vehicle routing problem
• An additive bounding procedure for the asymmetric travelling salesman problem
• New lower bounds for the symmetric travelling salesman problem
• A new dominance procedure for combinatorial optimization problems
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The complexity of the capacitated tree problem
• The Capacitated Minimum Spanning Tree
• Computing capacitated minimal spanning trees efficiently
• A branch and bound algorithm for the capacitated minimum spanning tree problem

Cited In (6)

• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• Models, relaxations and exact approaches for the capacitated vehicle routing problem
• Title not available (Why is that?)
• The (K,k)-Capacitated Spanning Tree Problem
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem
• Formulations and exact algorithms for the vehicle routing problem with time windows

Uses Software

• VRP

This page was built for publication: An exact algorithm for the capacitated shortest spanning arborescence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908299)