## Finding the Most Relevant Fragments in Networks

We study a cluster-identification type problem on networks motivated by applications in geographical analysis. 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.

keywords: Computational Geometry, Geographical Information Analysis, Graphs Theory

### Journal Article (peer-reviewed)

Bettina Speckmann, Günter Rote, Joachim Gudmundsson, Jun Luo, Kevin Buchin, Maarten Löffler, Rodrigo I. Silveira, Sergio Cabello, Thomas Wolle

Finding the Most Relevant Fragments in Networks

Journal of Graph Algorithms and Applications

14, 2, 307–336, 2010

### Conference Proceedings (peer-reviewed)

Bettina Speckmann, Günter Rote, Joachim Gudmundsson, Jun Luo, Kevin Buchin, Maarten Löffler, Rodrigo I. Silveira, Sergio Cabello, Thomas Wolle

Detecting Hotspots in Geographic Networks

Proc. 12th AGILE Conference on Geographic Information Science

217–231, 2009

*Best Paper Award*

back to list