Fast heuristics for vertex cover problem
| Autor: | Tolj, Bruno |
|---|---|
| Přispěvatelé: | Rudec, Tomislav, Baumgartner, Alfonzo |
| Jazyk: | chorvatština |
| Rok vydání: | 2020 |
| Předmět: | |
| Popis: | Cilj ovog završnog rada bio je napisati algoritam za rješavanje problema vršnog pokrivača iz teorije grafova. Algoritam je napisan u programskom jeziku C++. Rad je podjeljen na pet poglavlja. Nakon uvoda u drugom poglavlju problem je stavljen u kontekst s ostalim problemima vezanim uz teoriju grafova i NP-potpunu klasu problema. U trećem poglavlju opisani su i uspoređeni postojeći algoritmi prema brzini izvođenja i točnosti. Četvrto poglavlje bavi se posebnim slučajevima koji se mogu lakše rješiti i pravilima za grafove pomoću kojih se sužava mogući raspon rješenja. U petom poglavlju objašnjen je novi algoritam i uspoređen sa drugim algoritmima navedenima u ovome radu. The goal of this paper was writing an algorithm for solving the vertex cover problem from graph theory. The algorithm is written in the C++ programming language. The paper is split into five chapters. After introduction in the second chapter the problem is put into context with other problems in graph theory and the NP-complete class. In the third chapter existing algorithms are described and compared based on execution speed and accuracy. The forth chapter deals with special cases which can be solved easier and graph rules which help narrow down the range of possible solutions. In the fifth chapter the new algorithm is explained and compared with other algorithms listed in this paper. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|