Modifying networks to obtain low cost trees

DOI10.1007/3-540-62559-3_24MaRDI QIDQ6550552zbMATH OpenFDO

Authors Sven O. Krumke, Hartmut Noltemeier, Madhav V. Marathe, S. S. Ravi, Kay U. Drangmeister

Publication date 5 June 2024

zbMATH Keywords

computational complexityapproximation algorithmsNP-hardnesslocation theoryparametric search

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• Modifying edges of a network to obtain short subgraphs
• The constrained minimum spanning tree problem
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• Approximation algorithms for certain network improvement problems

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263177 (Why is no real title available?)
• scientific article; zbMATH DE number 871953 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Improving the location of minisum facilities through network modification
• Many birds with one stone
• Optimal attack and reinforcement of a network
• Routing to Multiple Destinations in Computer Networks
• The complexity of designing a network with minimum diameter

This page was built for publication: Modifying networks to obtain low cost trees

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