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:	Generalization Efficient algorithm Node (networking) Radius Tree (graph theory) Computer Science Applications Theoretical Computer Science Running time Combinatorics Signal Processing Graph (abstract data type) Graph algorithms Algorithm Information Systems Mathematics
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
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::565ecf67ba5f2e82aad0aa4c61b9b37a https://doi.org/10.1016/j.ipl.2008.12.009 Zobrazit plný text záznamu Full Text from ScienceDirect