Original title:
Značkování grafů
Translated title:
Graph labeling
Authors:
Böhm, Martin ; Mareš, Martin (advisor) ; Balyo, Tomáš (referee) Document type: Bachelor's theses
Year:
2011
Language:
eng Abstract:
[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
Keywords:
compression; graph theory; universal structures; komprese; teorie grafů; univerzální struktury
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/50632