Finding the Most Relevant Fragments in Networks
Kevin Buchin, Sergio Cabello, Joachim Gudmundsson, Maarten Löffler, Jun Luo, Günter Rote, Rodrigo I. Silveira, Bettina Speckmann, and Thomas Wolle
Vol. 14, no. 2, pp. 307-336, 2010. Regular paper.
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 non-negative 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 or a tree. We give polynomial-time algorithms, NP-hardness and NP-completeness proofs, approximation algorithms, and also fixed-parameter tractable algorithms.
Submitted: October 2009.
Reviewed: January 2010.
Revised: March 2010.
Accepted: April 2010.
Final: May 2010.
Published: June 2010.
Communicated by Dorothea Wagner
article (PDF)