20.500.12556/RUL-103882 Eksperimentalno ovrednotenje algoritmov za problem razmeščanja centrov magistrsko delo Experimental Evaluation of Algorithms for the Vertex k-center Problem V magistrskem delu predstavimo in implementiramo algoritme za reševanje problema razmeščanja centrov. Osredotočimo se na obstoječe približne algoritme. Razvijemo tudi nov natančen algoritem, ki je občutno hitrejši od izčrpnega preiskovanja. Za potrebe testiranja implementiramo generator naključnih testnih primerov za različne strukture grafov. Ta podpira generiranje naključnih povezanih grafov, dvodimenzionalnih mrež in brezlestvičnih omrežij. Našo implementacijo približnih algoritmov preverimo na standardni knjižnici testnih primerov in na primerih, generiranih z našim generatorjem. Za približne algoritme primerjamo razmerje med časom izvajanja in kakovostjo rešitve. In this thesis we present and implement algorithms for the $k$-center problem. We focus on existing heuristic algorithms. We also develop a new exact algorithm and show its superiority over the exhaustive enumeration. For testing purposes we implemented a random graph generator. It can generate random connected graphs, two-dimensional grids and scale-free networks. Our implementation of algorithms was tested on the standard test suite and the graphs generated by our generator. We also compare the ratio between computation time and result quality of heuristic algorithms. algoritmi na grafih kombinatorična optimizacija razmeščanje centrov graph algorithms combinatorial optimization vertex k-center true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2018-09-28 07:45:33 2018-09-28 07:45:35 2025-09-17 13:20:19 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.8 92616 18455129 RAZ_Elersic_Miha_i2018.pdf RAZ_Elersic_Miha_i2018.pdf 1 9E9D96E51C99EB5647A83BD795C2FF40 3b7a971b08f2ceea29c03daa35824c04876882330d796a00ef63ce172a5c7834 0e453893-a1b6-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=115429 Fakulteta za matematiko in fiziko Fakulteta za računalništvo in informatiko 0 0 0