## 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
### Abstract

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.

Last update: July 22, 2010.