Improving spanning trees by upgrading nodes

DOI10.1016/S0304-3975(99)00030-4zbMath0930.68003MaRDI QIDQ1960523

R. Ravi, Sven O. Krumke, Madhav V. Marathe, Hartmut Noltemeier, Hans-Christoph Wirth

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

spanning treenetwork designapproximation algorithmsNP-hardness

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Related Items

Improving multicut in directed trees by upgrading nodes ⋮ Optimizing cost flows by edge cost and capacity upgrade ⋮ Upgrading min-max spanning tree problem under various cost functions ⋮ Upgrading edges in the graphical TSP ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Competitive algorithms for the bicriteria \(k\)-server problem ⋮ Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies ⋮ A class of node based bottleneck improvement problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving the location of minisum facilities through network modification
• Modifying edges of a network to obtain short subgraphs
• On budget-constrained flow improvement.
• Graph minors. IV: Tree-width and well-quasi-ordering
• The Recognition of Series Parallel Digraphs
• An algebraic theory of graph reduction
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Network upgrading problems

This page was built for publication: Improving spanning trees by upgrading nodes