A linear time algorithm for computing minmax regret 1-median on a tree network
From MaRDI portal
Publication:486974
DOI10.1007/s00453-013-9851-7zbMath1317.05182OpenAlexW2001915330MaRDI QIDQ486974
Zhao Song, Tsunehiko Kameda, Binay K. Bhattacharya
Publication date: 19 January 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9851-7
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)
Related Items
A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint, Efficient algorithms for the minmax regret path center problem with length constraint on trees, A quadratic time exact algorithm for continuous connected 2-facility location problem in trees, Improved algorithms for computing minmax regret sinks on dynamic path and tree networks, An improved algorithm for the minmax regret path center problem on trees, Minimax regret 1-median problem in dynamic path networks, Minmax regret \(k\)-sink location on a dynamic path network with uniform capacities
Cites Work
- An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
- Efficient algorithms for two generalized 2-median problems and the group median problem on trees
- Robust discrete optimization and its applications
- Location science research: a review
- An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
- Robust location problems with pos/neg weights on a tree
- A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- An Algorithmic Approach to Network Location Problems. II: Thep-Medians
- Minmax-regret robust 1-median location on a tree
- Minmax Regret Median Location on a Network Under Uncertainty
- An improved algorithm for the minmax regret median problem on a tree
- Computing Minmax Regret 1-Median on a Tree Network with Positive/Negative Vertex Weights
- Improved algorithms for the minmax-regret 1-center and 1-median problems
