The obnoxious center problem on weighted cactus graphsZmazek, Blaž (Avtor) Žerovnik, Janez (Avtor) matematikaoperacijsko raziskovanjeteorija grafovlokacijski problemiproblem centranezaželjeni centrialgoritmi z linearno časovno zahtevnostjomathematicsoperations researchgraph theorylocation problemscenter problemobnoxious facilitieslinear time algorithmThe 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).20012015-07-10 14:52:38Članek v reviji51507sl