Název:
Značkování grafů
Překlad názvu:
Graph labeling
Autoři:
Böhm, Martin ; Mareš, Martin (vedoucí práce) ; Balyo, Tomáš (oponent) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
eng
Abstrakt: [eng][cze] We introduce the concept of adjacency labeling schemes and recent results in the area. These schemes have practical application in parallel algorithm design and they relate to the theory of universal graphs. We concentrate on the modern technique of "Traversal and Jumping". We present a less technical proof of its correctness as well as correcting some errors in the original proof. We also apply brute-force algorithms to find small induced-universal graphs. 1Práce představuje výsledky v oblasti schémat pro značkování grafů, která kódují sousednost vrcholů. Tato schémata mají praktické aplikace v oblasti paralelních algoritmů, souvisí však i s teorií univezál- ních grafů. Práce se soustředí na moderní metodu Traversal and Jumping, jejíž důkaz správnosti je zjednodušen a opraven. Také se zabýváme hledáním malých univerzálních grafů hrubou silou. 1
Klíčová slova:
komprese; teorie grafů; univerzální struktury; compression; graph theory; universal structures