Extending Partial Representations of Graphs
| Název práce v češtině: | Extending Partial Representations of Graphs |
|---|---|
| Název v anglickém jazyce: | Extending Partial Representations of Graphs |
| Klíčová slova: | Extension, Partial Representation, Graph |
| Klíčová slova anglicky: | Extension, Partial Representation, Graph |
| Akademický rok vypsání: | 2011/2012 |
| Typ práce: | diplomová 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í: | 06.04.2012 |
| Datum zadání: | 06.04.2012 |
| Datum potvrzení stud. oddělením: | 17.04.2012 |
| Datum a čas obhajoby: | 18.09.2012 10:00 |
| Datum odevzdání elektronické podoby: | 02.08.2012 |
| Datum odevzdání tištěné podoby: | 03.08.2012 |
| Datum proběhlé obhajoby: | 18.09.2012 |
| Oponenti: | doc. RNDr. Jiří Fiala, CSc. |
| Zásady pro vypracování |
| The student will study available literature on geometric representations of graphs with the goal of exploring the complexity of deciding if a partial representation can be extended to a full one. The classes of graphs that should be studied will include interval graphs, comparability graphs, circular arc graphs and others, of course those whose recognition (in the completely free case, when no partial representation is given) is known to be polynomial time decidable. |
| Seznam odborné literatury |
| F. R. Mcmorris, Terry A. Mckee: Topics in Intersection Graph Theory, SIAM 1999, ISBN-10-0898714303
M. C. Golumbic: Algorithmic Graph Theory and Perfect Graphs, 2nd Edition, North Holland 2004, ISBN 9780444515308 A. Brandstädt, Van Bang Le, J. P. Spinrad: Graph Classes: A Survey, SIAM 1999 J. Spinrad: Efficient Graph Representations, AMS 2003 journal literature following the advise of the tutor |