Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00209
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. 307336, 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 nonnegative 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 polynomialtime
algorithms, NPhardness and NPcompleteness proofs, approximation
algorithms, and also fixedparameter tractable algorithms.

Submitted: October 2009.
Reviewed: January 2010.
Revised: March 2010.
Accepted: April 2010.
Final: May 2010.
Published: June 2010.
Communicated by
Dorothea Wagner

Journal Supporters
