An algorithm for the single maximum coverage location or the -medianoid problem on trees

Autor: Joachim Spoerhase, Hans-Christoph Wirth
Rok vydání: 2009
Předmět:
Zdroj: Information Processing Letters. 109:391-394
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2008.12.009
Popis: The single maximum coverage location problem on a tree consists of placing one facility onto a node such that the total weight of users covered by the facility is maximized. Users are located at nodes of the tree. Each user has an individual sensitivity radius and is covered if and only if the facility is placed within that radius. This problem is a generalization of the (1,X"p)-medianoid problem (Hakimi, 1990). We provide a recursive graph coarsening algorithm which improves the running time from O(n^2) (Megiddo, 1983) to O(n(logn)^2/loglogn).
Databáze: OpenAIRE