Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem

DOI10.1145/322358.322367zbMath0504.90052MaRDI QIDQ4740330

Bezalel Gavish

Publication date: 1983

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322358.322367

zbMATH Keywords

heuristics; approximate solutions; Dantzig-Wolfe decomposition; integer linear programming; optimal solution; network design; communication network; computational tests; tight lower bounds; capacited minimal directed tree problem; Lagrangean relaxation procedure

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

65K05: Numerical mathematical programming methods

90C10: Integer programming

90C05: Linear programming

68R10: Graph theory (including graph drawing) in computer science

90B10: Deterministic network models in operations research

Related Items

Two Matching Based Algorithm for Tree Network Design, Topological Design of Centralized Computer Networks, Unnamed Item, Exact solution of the centralized network design problem on directed graphs, Globally and locally minimal weight spanning tree networks, Models for planning capacity expansion in local access telecommunication networks, Network flow models for the local access network expansion problem, Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms, A result on projection for the vehicle routing problem, Topological design of telecommunication networks --- local access design methods, Finding minimum cost directed trees with demands and capacities, Dynamic programming based heuristics for the topological design of local access networks, Configuration of fully replicated distributed database system over wide area networks, Topological design of wide area communication networks, Topological design of a centralized communication network with unreliable links and node outage costs, Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees, Heuristic procedure neural networks for the CMST problem, Generalized spanning trees, A survey on Benders decomposition applied to fixed-charge network design problems, The capacitated minimum spanning tree problem: revisiting hop-indexed formulations, A multiperiod degree constrained minimal spanning tree problem, The capacitated minimum spanning tree problem: On improved multistar constraints, An exact algorithm for the capacitated shortest spanning arborescence, Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs, A multiperiod planning model for the capacitated minimal spanning tree problem, Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, A Lagrangian based heuristic for the design of multipoint linkages in a communication network with unreliable links and node outage costs., Optimal buffer allocation in finite closed networks with multiple servers, Savings based ant colony optimization for the capacitated minimum spanning tree problem, A branch and bound algorithm for the capacitated minimum spanning tree problem, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, The Minimum Spanning Tree Problem with Time Window Constraints, Balanced spanning forests and trees, Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem