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

DOI10.1016/J.IPL.2008.12.009zbMath1191.68472OpenAlexW2080033794MaRDI QIDQ976129

Hans-Christoph Wirth, Joachim Spoerhase

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.12.009

zbMATH Keywords

treegraph algorithmsefficient algorithmcoveragemedianoid

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Improved algorithms for some competitive location centroid problems on paths, trees and graphs ⋮ \((r,p)\)-centroid problems on paths and trees ⋮ ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The budgeted maximum coverage problem
• An \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• The Maximum Coverage Location Problem
• Mixed covering of trees and the augmentation problem with odd diameter constraints

This page was built for publication: 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