magistrsko delo
Miha Eleršič (Author), Jurij Mihelič (Mentor)

Abstract

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.

Keywords

algoritmi na grafih;kombinatorična optimizacija;razmeščanje centrov;

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [M. Eleršič]
UDC: 519.8
COBISS: 18455129 Link will open in a new window
Views: 1211
Downloads: 213
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Experimental Evaluation of Algorithms for the Vertex k-center Problem
Secondary abstract: 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.
Secondary keywords: graph algorithms;combinatorial optimization;vertex k-center;
Type (COBISS): Master's thesis/paper
Study programme: 0
Thesis comment: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Pages: VII, 56 str.
ID: 10962322