TY - GEN

T1 - Detecting Hotspots in Geographic Networks

AU - Buchin, Kevin

AU - Cabello, Sergio

AU - Gudmundsson, Joachim

AU - Löffler, Maarten

AU - Luo, Jun

AU - Rote, Günter

AU - Silveira, Rodrigo I.

AU - Speckmann, Bettina

AU - Wolle, Thomas

N1 - bcgllrssw-cars-09 Best paper award
Inaugurele rede uitgesproken 28 april 2009 Utrecht

PY - 2009

Y1 - 2009

N2 - We study a cluster-identification type problem on networks motivated by applications in geographical analysis. Given a network N (a connected graph with positive edge lengths) together with a set of sites, which lie on the edges or vertices of N, we look for a connected subnetwork F of N of small total length that contains many sites. The edges of F can form parts of the edges of N. We consider different variants of this problem where N is either a general graph or restricted to a tree, and the subnetwork F that we are looking for is either a simple path, a path with self-intersections at vertices, or a tree. We give polynomial-time algorithms, NP-hardness and NP-completeness proofs, approximation algorithms, and also fixed-parameter tractable algorithms.

AB - We study a cluster-identification type problem on networks motivated by applications in geographical analysis. Given a network N (a connected graph with positive edge lengths) together with a set of sites, which lie on the edges or vertices of N, we look for a connected subnetwork F of N of small total length that contains many sites. The edges of F can form parts of the edges of N. We consider different variants of this problem where N is either a general graph or restricted to a tree, and the subnetwork F that we are looking for is either a simple path, a path with self-intersections at vertices, or a tree. We give polynomial-time algorithms, NP-hardness and NP-completeness proofs, approximation algorithms, and also fixed-parameter tractable algorithms.

KW - CG, GIS, GRAPH

U2 - 10.1007/978-3-642-00318-9_11

DO - 10.1007/978-3-642-00318-9_11

M3 - Conference contribution

SP - 217

EP - 231

BT - Proc. 12th AGILE Conference on Geographic Information Science

A2 - Sester, M.

A2 - Bernard, L.

A2 - Paelke, V.

PB - Springer

ER -