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
http://dx.doi.org/10.7155/jgaa.00209

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
http://dx.doi.org/10.1007/978-3-642-00318-9_11
Best Paper Award

back to list