\((r,p)\)-centroid problems on paths and trees

DOI10.1016/J.TCS.2009.08.020zbMath1176.90364OpenAlexW1977137429MaRDI QIDQ1034634

Joachim Spoerhase, Hans-Christoph Wirth

Publication date: 6 November 2009

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

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

zbMATH Keywords

computational complexitytreesefficient algorithmscompetitive location

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

The \(w\)-centroids and least \(w\)-central subtrees in weighted trees ⋮ Improved algorithms for some competitive location centroid problems on paths, trees and graphs ⋮ Trees with unique least central subtrees ⋮ A local search heuristic for the \((r| p)\)-centroid problem in the plane ⋮ \((r|p)\)-centroid problems on networks with vertex and edge demand ⋮ Multi-depot traveling salesmen location problems on networks with special structure ⋮ Optimal strategies for the one-round discrete Voronoi game on a line ⋮ An exact procedure and LP formulations for the leader-follower location problem ⋮ An exact method for the discrete \((r|p)\)-centroid problem ⋮ A kernel search matheuristic to solve the discrete leader-follower location problem ⋮ Sequential competitive location on networks ⋮ Fast metaheuristics for the discrete \((r|p)\)-centroid problem ⋮ How to Calculate the Barycenter of a Weighted Graph ⋮ \((r,p)\)-centroid problems on paths and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiple voting location and single voting location on trees
• The leader-follower location model
• Multiple voting location problems
• An \(O(n(\log n)^{2}/\log \log n)\) algorithm for the single maximum coverage location or the \((1,X_p)\)-medianoid problem on trees
• \((r,p)\)-centroid problems on paths and trees
• On locating new facilities in a competitive environment
• Sequential location problems
• Relaxation of the Condorcet and Simpson conditions in voting location
• On \(k\)-sum optimization
• The Maximum Coverage Location Problem
• Algorithms for Voting and Competitive Location on a Network

This page was built for publication: \((r,p)\)-centroid problems on paths and trees