02055516

j

02055516 Zmazek, Bla\v z \v Zerovnik, Janez The obnoxious center problem on weighted cactus graphs. Discrete Appl. Math. 136, No. 2-3, 377-386 (2004). 2004 Elsevier Science B.V. (North-Holland), Amsterdam EN Location problems Center problem Obnoxious facilities Linear-time algorithm

doi:10.1016/S0166-218X(03)00452-9

Summary: The obnoxious center problem in a graph $G$ asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. An algorithm is given which finds the obnoxious center on a weighted cactus graph in O($cn$) time, where $n$ is the number of vertices and $c$ is the number of different vertex weights (called marks).