Extending Partial Representations of Graphs
| Thesis title in Czech: | Extending Partial Representations of Graphs |
|---|---|
| Thesis title in English: | Extending Partial Representations of Graphs |
| Key words: | Extension, Partial Representation, Graph |
| English key words: | Extension, Partial Representation, Graph |
| Academic year of topic announcement: | 2011/2012 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Applied Mathematics (32-KAM) |
| Supervisor: | prof. RNDr. Jan Kratochvíl, CSc. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 06.04.2012 |
| Date of assignment: | 06.04.2012 |
| Confirmed by Study dept. on: | 17.04.2012 |
| Date and time of defence: | 18.09.2012 10:00 |
| Date of electronic submission: | 02.08.2012 |
| Date of submission of printed version: | 03.08.2012 |
| Date of proceeded defence: | 18.09.2012 |
| Opponents: | doc. RNDr. Jiří Fiala, CSc. |
| Guidelines |
| 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. |
| References |
| 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 |