Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun Luo, Günter Rote, Rodrigo I. Silveira, Bettina Speckmann, and Thomas Wolle:

1. Detecting hotspots in geographic networks

In: Advances in GIScience. Proceedings of the 12th AGILE International Conference on Geographic Information Science, Hannover, Germany, June 2009, Editors: Monika Sester, Lars Bernard, Volker Paelke. Lecture Notes in Geoinformation and Cartography, Springer-Verlag, 2009, pp. 217–231. (Best paper award). doi:10.1007/978-3-642-00318-9_11

2. Finding the most relevant fragments in networks

Journal of Graph Algorithms and Applications 14 (2010), 307–336. doi:10.7155/jgaa.00209


We study a point pattern detection problem on networks, motivated by applications in geographical analysis, such as crime hotspot detection. 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.

  pdf file (gzipped)
other papers about this subject
Last update: July 22, 2010.