Finding the most relevant fragments in networks

K. Buchin, S. Cabello, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R.I. Silveira, B. Speckmann, T. Wolle

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)
92 Downloads (Pure)


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.
Originele taal-2Engels
Pagina's (van-tot)307-336
Aantal pagina's30
TijdschriftJournal of Graph Algorithms and Applications
Nummer van het tijdschrift2
StatusGepubliceerd - 2010

Vingerafdruk Duik in de onderzoeksthema's van 'Finding the most relevant fragments in networks'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Buchin, K., Cabello, S., Gudmundsson, J., Löffler, M., Luo, J., Rote, G., Silveira, R. I., Speckmann, B., & Wolle, T. (2010). Finding the most relevant fragments in networks. Journal of Graph Algorithms and Applications, 14(2), 307-336.