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

DOI10.1016/J.TCS.2009.08.020MaRDI QIDQ1034634zbMATH OpenOpenAlexFDO

Authors Joachim Spoerhase, H.-C. 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

competitive locationcomputational complexityefficient algorithmstrees

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2081036
• On the complexity of the \((r|p)\)-centroid problem in the plane
• The p-center problem in tree networks revisited
• scientific article; zbMATH DE number 1744100
• The generalized discrete ‐centroid problem
• The Round-Trip p-Center and Covering Problem on a Tree
• Algorithms for central-median paths with bounded length on trees
• A branch-and-cut algorithm for the discrete \((r| p)\)-centroid problem
• scientific article; zbMATH DE number 5732600
• The weighted \(k\)-center problem in trees for fixed \(k\)

Cites work

• \((r,p)\)-centroid problems on paths and trees
• Algorithms for Voting and Competitive Location on a Network
• 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
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 9247 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 961964 (Why is no real title available?)
• Multiple voting location and single voting location on trees
• Multiple voting location problems
• NP-hardness of some competitive location models with probabilistic choice rules
• On \(k\)-sum optimization
• On locating new facilities in a competitive environment
• Relaxation of the Condorcet and Simpson conditions in voting location
• Sequential location problems
• The leader-follower location model
• The Maximum Coverage Location Problem

Cited in

(17)

• \((r,p)\)-centroid problems on paths and trees
• The w-centroids and least w-central subtrees in weighted trees
• Trees with unique least central subtrees
• Multi-depot traveling salesmen location problems on networks with special structure
• Improved algorithms for some competitive location centroid problems on paths, trees and graphs
• A local search heuristic for the \((r| p)\)-centroid problem in the plane
• \((r|p)\)-centroid problems on networks with vertex and edge demand
• scientific article; zbMATH DE number 5732600 (Why is no real title available?)
• Optimal strategies for the one-round discrete Voronoi game on a line
• Sequential competitive location on networks
• A polynomial algorithm for thep-centdian problem on a tree
• On the complexity of the \((r|p)\)-centroid problem in the plane
• Fast metaheuristics for the discrete \((r|p)\)-centroid problem
• How to calculate the barycenter of a weighted graph
• An exact procedure and LP formulations for the leader-follower location problem
• A kernel search matheuristic to solve the discrete leader-follower location problem
• An exact method for the discrete \((r|p)\)-centroid problem

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

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