Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
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. 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. Accepted: April 2010. Revised: March 2010. Published: June 2010. Final: May 2010. Communicated by Dorothea Wagner |
| Journal of Graph Algorithms and Applications |