Graph labeling

• Thesis title in Czech: Značkování grafů
• Thesis title in English: Graph labeling
• Key words: teorie grafů, komprese, univerzální struktury
• English key words: graph theory, compression, universal structures
• Academic year of topic announcement: 2010/2011
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: Mgr. Martin Mareš, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 10.11.2010
• Date of assignment: 10.11.2010
• Date and time of defence: 07.09.2011 09:00
• Date of electronic submission: 08.08.2011
• Date of submission of printed version: 05.08.2011
• Date of proceeded defence: 07.09.2011
• Opponents: RNDr. Tomáš Balyo, Ph.D.

Guidelines

Ú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í.

References

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.