Upgrading min-max spanning tree problem under various cost functions

DOI10.1016/j.tcs.2017.08.006zbMath1382.68123OpenAlexW2752698094MaRDI QIDQ1680539

Ehsan Monabbati, Ali Reza Sepasian

Publication date: 16 November 2017

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.08.006

zbMATH Keywords

location problemsmin-max spanning treeupgrading problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

Upgrading the 1-center problem with edge length variables on a tree ⋮ Upgrading edges in the maximal covering location problem ⋮ Upgrading edges in the graphical TSP ⋮ The \(p\)-median problem with upgrading of transportation costs and minimum travel time allocation ⋮ Speedup the optimization of maximal closure of a node-weighted directed acyclic graph ⋮ A note on upgrading the min–max weight of a base of a matroid ⋮ Optimal algorithms for inverse obnoxious center location problems under the weighted Chebyshev and Hamming cost norms on networks ⋮ Further Study on Reverse 1-Center Problem on Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Upgrading \(p\)-median problem on a path
• Inverse min-max spanning tree problem under the weighted sum-type Hamming distance
• Up- and downgrading the 1-center in a network
• Constrained inverse min-max spanning tree problems under the weighted Hamming distance
• The Min-Max Spanning Tree Problem and some extensions
• Modifying edges of a network to obtain short subgraphs
• Approximation algorithms for certain network improvement problems
• Lagrangian and branch-and-cut approaches for upgrading spanning tree problems
• Improving spanning trees by upgrading nodes
• A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric
• The Constrained Bottleneck Problem in Networks
• Stochastic bottleneck spanning tree problem
• Maximizing the minimum source-sink path subject to a budget constraint
• Edge Weight Reduction Problems in Directed Acyclic Graphs
• Improving spanning trees by upgrading nodes
• Minimum bottleneck spanning trees with degree bounds
• Network upgrading problems
• An Improved Algorithm for the Constrained Bottleneck Spanning Tree Problem
• Increasing the Weight of Minimum Spanning Trees
• The network inhibition problem

This page was built for publication: Upgrading min-max spanning tree problem under various cost functions