| Meno: | Martin
|
|---|
| Priezvisko: | Námešný
|
|---|
| Názov: | Aproximačné algoritmy na určenie priesečníkového čísla grafov
|
|---|
| Vedúci: | doc. RNDr. Rastislav Královič, PhD
|
|---|
| Rok: | 2008
|
|---|
| Kľúčové slová: | lineárne priesečníkové číslo, fixované lineárne priesečníkové číslo, heuristiky, aproximácie
|
|---|
| Abstrakt: | V tejto práci sa venujem heuristikám, ktoré minimalizujú lineárne priesečníkové číslo a lineárne priesečníkové číslo s fixovanou permutáciou vrcholov. V prvej časti popisujem princíp a popis algoritmov a v ďalšej časti porovnávam jednotlivé heuristiky podľa výsledkov, ktoré dosiahli na niekoľkých triedach grafov. V práci sú použité algoritmy rôznych druhov od jednoduchých greedy algoritmov, cez neurónové siete a semidefinitné programovanie až po genetický algoritmus a simulované žíhanie.
|
|---|