Computational Complexity of Graph Planarity Testing
Název práce v češtině: | Výpočetní složitost testování rovinnosti grafu |
---|---|
Název v anglickém jazyce: | Computational Complexity of Graph Planarity Testing |
Akademický rok vypsání: | 2005/2006 |
Typ práce: | bakalářská práce |
Jazyk práce: | angličtina |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | Mgr. Martin Bálek |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 03.11.2005 |
Datum zadání: | 03.11.2005 |
Datum a čas obhajoby: | 27.06.2006 00:00 |
Datum odevzdání elektronické podoby: | 27.06.2006 |
Datum odevzdání tištěné podoby: | 27.06.2006 |
Datum proběhlé obhajoby: | 27.06.2006 |
Oponenti: | Mgr. Petr Škovroň, Ph.D. |
Zásady pro vypracování |
Práce bude v angličtině. |
Seznam odborné literatury |
V. Ramachandran, J. Reiff: Planarity Testing in Parallel, J. Computer and Systems Sciences vol.49, 1994
J. Reiff: Symmetric Complementation, J. of ACM, 1984 E. Allender, M. Mahajan: The Complexity of Planarity Testing M. Sipser: Introduction to the Thory of Computation, PWS Publishing, 1997 |
Předběžná náplň práce |
Problému planarity grafu je v LOGSPACE. Práce bude obsahovat (LOGSPACE) algoritmus
redukce libovolného grafu na graf s maximálním stupněm 3. Jedná se o zjednodušení postupu z článku Allenrder, Mahajan: The Complexity of Planarity Testing. |