Modifying edges of a network to obtain short subgraphs

DOI10.1016/S0304-3975(97)00290-9zbMath0913.68144OpenAlexW1967463818MaRDI QIDQ1274323

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

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00290-9

zbMATH Keywords

network designapproximation algorithmsNP-hardnessspanning-tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Efficient algorithms for robustness in resource allocation and scheduling problems ⋮ Upgrading trees under diameter and budget constraints ⋮ Optimal approaches for upgrading selective obnoxious \(p\)-median location problems on tree networks ⋮ Upgrading the 1-center problem with edge length variables on a tree ⋮ 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 ⋮ Upgrading \(p\)-median problem on a path ⋮ Speedup the optimization of maximal closure of a node-weighted directed acyclic graph ⋮ Weight reduction problems with certain bottleneck objectives. ⋮ Improving spanning trees by upgrading nodes ⋮ Reverse 2-median problem on trees ⋮ Bottleneck Capacity Expansion Problems with General Budget Constraints ⋮ Complexity of reducing the delay between two nodes by node-based and edge-based upgrading strategies ⋮ A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric ⋮ A class of node based bottleneck improvement problems ⋮ Up- and downgrading the 1-center in a network ⋮ The non-approximability of bicriteria network design problems ⋮ Some inverse optimization problems under the Hamming distance ⋮ On budget-constrained flow improvement.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improving the location of minisum facilities through network modification
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• An 11/6-approximation algorithm for the network Steiner problem
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Parallel Merge Sort
• Approximation Schemes for the Restricted Shortest Path Problem
• Bicriteria Network Design Problems
• Biconnectivity approximations and graph carvings
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Linear-time computation of optimal subgraphs of decomposable graphs
• Increasing the Weight of Minimum Spanning Trees
• Improving Minimum Cost Spanning Trees by Upgrading Nodes
• The constrained minimum spanning tree problem
• Many birds with one stone