Graph labeling

• Název práce v češtině: Značkování grafů
• Název v anglickém jazyce: Graph labeling
• Klíčová slova: teorie grafů, komprese, univerzální struktury
• Klíčová slova anglicky: graph theory, compression, universal structures
• Akademický rok vypsání: 2010/2011
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Mareš, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 10.11.2010
• Datum zadání: 10.11.2010
• Datum a čas obhajoby: 07.09.2011 09:00
• Datum odevzdání elektronické podoby: 08.08.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 07.09.2011
• Oponenti: RNDr. Tomáš Balyo, Ph.D.

Zásady pro vypracování

Úkolem studenta je seznámit se s technikami reprezentace grafů pomocí značkování vrcholů (vertex labeling) a se souvislostmi mezi značkováním a univerzálními grafy. Práce by měla obsahovat přehled známých technik pro jednotlivé třídy grafů a případně se pokusit o jejich vylepšení nebo zobecnění.

Seznam odborné literatury

C. Gavoille, A. Labourel: Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs.

M. Thorup: Compact Oracles for Reachability and Approximate Distances in Planar Digraphs.