Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem

DOI10.1145/322358.322367zbMath0504.90052OpenAlexW2012682597MaRDI 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

heuristicsapproximate solutionsDantzig-Wolfe decompositioninteger linear programmingoptimal solutionnetwork designcommunication networkcomputational teststight lower boundscapacited minimal directed tree problemLagrangean relaxation procedure

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items (49)

Topological design of a centralized communication network with unreliable links and node outage costs ⋮ The capacitated minimum spanning tree problem: On improved multistar constraints ⋮ Unnamed Item ⋮ Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: Properties and algorithms ⋮ Balanced spanning forests and trees ⋮ A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem ⋮ Network flow models for the local access network expansion problem ⋮ Looking for edge-equitable spanning trees ⋮ A biased random-key genetic algorithm for the capacitated minimum spanning tree problem ⋮ An exact algorithm for the capacitated shortest spanning arborescence ⋮ A node rooted flow-based model for the local access network expansion problem ⋮ Two Matching Based Algorithm for Tree Network Design ⋮ Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem ⋮ A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks ⋮ A result on projection for the vehicle routing problem ⋮ The \((K, k)\)-capacitated spanning tree problem ⋮ Computational comparisons of different formulations for the Stackelberg minimum spanning tree game ⋮ The Minimum Spanning Tree Problem with Time Window Constraints ⋮ RAMP for the capacitated minimum spanning tree problem ⋮ Tree network design avoiding congestion ⋮ Heuristics for the multi-level capacitated minimum spanning tree problem ⋮ Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs ⋮ A multiperiod planning model for the capacitated minimal spanning tree 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 ⋮ Topological Design of Centralized Computer Networks ⋮ 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 ⋮ Configuration of fully replicated distributed database system over wide area networks ⋮ Topological design of wide area communication networks ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ Clustering data that are graph connected ⋮ A survey on Benders decomposition applied to fixed-charge network design problems ⋮ The capacitated minimum spanning tree problem: revisiting hop-indexed formulations ⋮ Globally and locally minimal weight spanning tree networks ⋮ Exact solution approaches for the multi-period degree constrained minimum spanning tree problem ⋮ Exact solution of the centralized network design problem on directed graphs ⋮ A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem ⋮ Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees ⋮ Heuristic procedure neural networks for the CMST problem ⋮ Generalized spanning trees ⋮ Design of capacitated degree constrained min-sum arborescence ⋮ A multiperiod degree constrained minimal spanning tree problem ⋮ Savings based ant colony optimization for the capacitated minimum spanning tree problem ⋮ Models for planning capacity expansion in local access telecommunication networks ⋮ A branch and bound algorithm for the capacitated minimum spanning tree problem ⋮ Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality

This page was built for publication: Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem