### 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.

Original language | English |
---|---|

Pages (from-to) | 307-336 |

Number of pages | 30 |

Journal | Journal of Graph Algorithms and Applications |

Volume | 14 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2010 |

## Fingerprint Dive into the research topics of 'Finding the most relevant fragments in networks'. Together they form a unique fingerprint.

## Cite this

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