VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Finding the most relevant fragments in networks [Elektronski vir]
    Buchin, Kevin ...
    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, 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.
    Vir: Journal of graph algorithms and applications [Elektronski vir]. - ISSN 1526-1719 (Vol. 14, no. 2, 2010, str. 307-336)
    Vrsta gradiva - e-članek
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 15629401

    Povezava(-e):

    http://jgaa.info/accepted/2010/Buchin+2010.14.2.pdf

Vnos na polico