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.