20.500.12556/DKUM-51507 The obnoxious center problem on weighted cactus graphs Problem nezaželenega centra na obteženih kaktus grafih 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). Problem nezaželenih centrov v grafu predstavlja določitev takšne lokacije na povezavah grafa, da je njena minimalna razdalja do poljubne točke grafa kolikor se da velika. Uteži na točkah grafa lahko predstavljajo njihovo občutljivost, ki jo je moč oceniti z eno izmed konstantno mnogo vrednosti. Kadar je vsaki točki grafa prirejena ena izmed ▫$c$▫ različnih vrednosti (uteži) glede na njeno občutljivost, rešujemo tako imenovan problem nezaželenih centrov na grafu z ovrednotenimi točkami. V tem članku bomo predstavili algoritem, ki določi nezaželeni center na kaktusu z ovrednotenimi točkami v linearnem času ▫$O(cn)$▫, kjer je ▫$n$▫ število točk in ▫$c$▫ število uteži. 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). matematika operacijsko raziskovanje teorija grafov lokacijski problemi problem centra nezaželjeni centri algoritmi z linearno časovno zahtevnostjo mathematics operations research graph theory location problems center problem obnoxious facilities linear time algorithm true true false Angleški jezik Neznan jezik Članek v reviji 2015-07-10 14:52:38 2015-07-10 14:52:38 2024-03-05 14:09:11 2019-07-11 07:20:54 2001 0 0 str. 133-136 Vol. 8 May, 2001 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.86:519.17 13803097 13824345 1571-0653 URN:SI:UM:DK:BSM23PYM http://dx.doi.org/10.1016/S1571-0653(05)80099-X 1 https://dk.um.si/Dokument.php?lang=slv&id=76067 Pedagoška fakulteta 0 0 0