Geometrické reprezentace grafů

• Název práce v češtině: Geometrické reprezentace grafů
• Název v anglickém jazyce: Geometric representations of graphs
• Akademický rok vypsání: 2009/2010
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. RNDr. Jan Kratochvíl, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.11.2009
• Datum zadání: 09.11.2009
• Datum a čas obhajoby: 17.09.2010 00:00
• Datum odevzdání elektronické podoby: 17.09.2010
• Datum proběhlé obhajoby: 17.09.2010
• Oponenti: RNDr. Martin Pergel, Ph.D.

Zásady pro vypracování

The student will study geometric representations of graphs such as intersection graphs, inclusion representations, geometrically motivated discrete structures and others. Main attention will be paid to recongition of such structures and algorithms for the basic optimization problems on them.

Seznam odborné literatury

McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, Philadelphia: Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2), MR1672910, ISBN 0-89871-430-3

Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

aktuální časopisecká literatura podle zadání vedoucího

Předběžná náplň práce

Geometrické reprezentace grafů, jejich rozpoznávání a algoritmy na nich.

Předběžná náplň práce v anglickém jazyce

Geometric representations of graphs, their recognition and algorithms on them.