Finding the Most Relevant Fragments in Networks
文献类型：期刊论文
| 作者 | Kevin Buchin; Sergio Cabello; Joachim Gudmundsson; Maarten L¨offler; Jun Luo; G¨unter Rote; Rodrigo I. Silveira; Bettina Speckmann; Thomas Wolle |
| 刊名 | Journal of Graph Algorithms and Applications
 |
| 出版日期 | 2010 |
| 卷号 | 14期号:2页码:307-336 |
| 英文摘要 | 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 al-gorithms, and also fixed-parameter tractable algorithms. |
| 收录类别 | 其他 |
| 原文出处 | http://jgaa.info/accepted/2010/Buchin+2010.14.2.pdf |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/3093]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | Journal of Graph Algorithms and Applications |
| 推荐引用方式 GB/T 7714 | Kevin Buchin,Sergio Cabello,Joachim Gudmundsson,et al. Finding the Most Relevant Fragments in Networks[J]. Journal of Graph Algorithms and Applications,2010,14(2):307-336. |
| APA | Kevin Buchin.,Sergio Cabello.,Joachim Gudmundsson.,Maarten L¨offler.,Jun Luo.,...&Thomas Wolle.(2010).Finding the Most Relevant Fragments in Networks.Journal of Graph Algorithms and Applications,14(2),307-336. |
| MLA | Kevin Buchin,et al."Finding the Most Relevant Fragments in Networks".Journal of Graph Algorithms and Applications 14.2(2010):307-336. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。