Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem

DOI10.1145/322358.322367MaRDI QIDQ4740330zbMATH OpenOpenAlexFDO

Authors 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

approximate solutionscapacited minimal directed tree problemcommunication networkcomputational testsDantzig-Wolfe decompositionheuristicsinteger linear programmingLagrangean relaxation procedurenetwork designoptimal solutiontight lower bounds

Mathematics Subject Classification ID

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

Cited in

(50)

• A model for the capacitated, hop-constrained, per-packet wireless mesh network design 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
• 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
• 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
• The \((K, k)\)-capacitated 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
• Design of capacitated degree constrained min-sum arborescence
• A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem
• RAMP for the capacitated minimum spanning tree problem
• Heuristics for the multi-level capacitated minimum 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 node rooted flow-based model for the local access network expansion problem
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• Looking for edge-equitable spanning trees
• A biased random-key genetic 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
• Two Matching Based Algorithm for Tree Network Design
• Topological Design of Centralized Computer Networks
• scientific article; zbMATH DE number 1420487 (Why is no real title available?)
• A branch-and-bound algorithm for building optimal data gathering tree in wireless sensor networks
• Exact solution of the centralized network design problem on directed graphs
• Globally and locally minimal weight spanning tree networks
• Computational comparisons of different formulations for the Stackelberg minimum spanning tree game
• Tree network design avoiding congestion
• The ordered median tree location problem
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
• Models for planning capacity expansion in local access telecommunication networks
• Network flow models for the local access network expansion problem

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

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