The non-approximability of bicriteria network design problems

DOI10.1016/S1570-8667(03)00033-9zbMath1074.68040MaRDI QIDQ1827279

Vojtech Bálint

Publication date: 6 August 2004

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

zbMATH Keywords

NP-hardnessNetwork designDiameterSpanning treeNon-approximabilityBicriteria problemsRoot stretch factorStretch factor

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

The density maximization problem in graphs ⋮ Exact approaches for the minimum subgraph diameter problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the minimum diameter spanning tree problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Modifying edges of a network to obtain short subgraphs
• Approximation algorithms for certain network improvement problems
• Balancing minimum spanning trees and shortest-path trees
• The complexity of designing a network with minimum diameter
• Bicriteria Network Design Problems
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Spanning Trees—Short or Small
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: The non-approximability of bicriteria network design problems