Heuristics with Constant Error Guarantees for the Design of Tree Networks

DOI10.1287/MNSC.34.3.331zbMath0639.90096OpenAlexW2164581054MaRDI QIDQ3780780

Kemal Altinkemer, Bezalel Gavish

Publication date: 1988

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.34.3.331

zbMATH Keywords

NP-completenetwork designefficient heuristicpartitioning of a traveling salesman tourspanning tree network of minimum length

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Numerical mathematical programming methods (65K05)

Related Items (19)

Topological design of a centralized communication network with unreliable links and node outage costs ⋮ Heuristics for unequal weight delivery problems with a fixed error guarantee ⋮ Survivable network design: the capacitated minimum spanning network problem ⋮ Two Matching Based Algorithm for Tree Network Design ⋮ Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem ⋮ The \((K, k)\)-capacitated spanning tree problem ⋮ Size-constrained tree partitioning: approximating the multicast \(k\)-tree routing problem ⋮ On the complexity of graph tree partition problems. ⋮ A multiperiod planning model for the capacitated minimal spanning tree problem ⋮ Topological design of telecommunication networks --- local access design methods ⋮ Dynamic programming based heuristics for the topological design of local access networks ⋮ A Lagrangian based heuristic for the design of multipoint linkages in a communication network with unreliable links and node outage costs. ⋮ Topological design of computer communication networks -- the overall design problem ⋮ Analysis of heuristics for the design of tree networks ⋮ Hybrid fiber co-axial CATV network design with variable capacity optical network units ⋮ Heuristic procedure neural networks for the CMST problem ⋮ Design of capacitated degree constrained min-sum arborescence ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem ⋮ Algorithms for a multi-level network optimization problem

This page was built for publication: Heuristics with Constant Error Guarantees for the Design of Tree Networks