Bakalářská práce

Srovnání Vertex cover, Twin-cover a Neighborhood diversity na grafech

Comparison of Vertex cover, Twin-cover and Neighborhood diversity on graphs

Vladimír Lambert, učo 348230
Anotace

Tato práce srovnává hodnoty vrcholového pokrytí, twin-cover a neighborhood diversity na grafech. Po představení pojmů z teorie grafů vztahujících se k zadanému tématu jsou popsány algoritmy počítající tyto parametry. V závěru je porovnána velikost těchto parametrů pro různé grafy.

Abstract

This bachelor thesis compares values of vertex cover, twin-cover and neighborhood diversity on graphh. After introduction into terms from graph theory related to given topic, algorithms computing these parameters are described. At the end values of these parameters are compared for various graphs.

Klíčová slova
teorie grafů vrcholové pokrytí twin-cover neighborhood diversity parametrizovaná složitost
Zadání práce
The first goal of the thesis is to implement an efficient algorithm for computing the vertex cover of large, practically important graphs, such as those listed in TreewidthLIB or their suitable induced subgraphs. The second goal of the thesis is to then adapt this algorithm to also compute the so-called twin-cover and the neighborhood diversity of the same graphs. The output of the thesis will be the three algorithms and an overview of the tested graphs with the computed values of vertex cover, twin-cover and neighborhood diversity.
Administrativní informace
Práce zkontrolována:
7. 6. 2012 10:55, RNDr. Robert Ganian, Ph.D.
Plný text práce
331,3 KB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
22. 6. 2012
Práce byla úspěšně obhájena

Vedoucí

RNDr. Robert Ganian, Ph.D.
ext KTP FI MU

Oponent

RNDr. Ondrej Moriš, učo 172887
abs FI MU

Literatura

  • GROHE, Martin. Parameterized complexity theory. Edited by Jörg Flum. Berlin: Springer, 2006, xiii, 493. ISBN 3540299521.
  • DIESTEL, Reinhard. Graph theory. 3rd ed. Berlin: Springer, 2006, xvi, 410s. ISBN 3540261834.
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.