A note on locating a central vertex of a 3-cactus graph (Q913638): Difference between revisions

This paper examines two location problems on vertex-weighted networks (graphs with edge-lengths, on which distance is calculated as shortest path distance). The minimum weighted vertex variance problem asks for the vertex at which the variance of the weighted distances to all vertices is minimized, while the vertex restricted stochastic queue median problem is to determine the vertex minimizing the mean service time from there to customer calls at each vertex, which occur independently as Poisson processes and are served as a queue. Known algorithms solving these problems in time linear in the number of vertices for tree networks are extended here to linear time algorithms on 3-cactus networks, i.e. networks in which the biconnected components consist of at most three vertices. This is achieved by a linear time transformation of the 3-cactus network to a tree on which shortest path- lengths are preserved.