hidden - assigned and confirmed by the Study Dept.
Date of registration:
06.10.2008
Date of assignment:
06.10.2008
Date and time of defence:
22.06.2009 00:00
Date of electronic submission:
22.06.2009
Date of proceeded defence:
22.06.2009
Opponents:
RNDr. Martin Pergel, Ph.D.
Guidelines
Student prostuduje doporučenou literaturu s cílem rozhodnout, zda Thomasonův algoritmus pro nalezení druhé Hamiltonovské kružnice v kubickém grafu potřebuje exponenciálně mnoho kroků při spuštění na libovolnou hranu Krawczykova grafu. Vodítkem může být počítačový experiment.
References
Kathie Cameron: Thomason's algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs. Discrete Mathematics 235(1-3): 69-77 (2001)
Adam Krawczyk: The complexity of finding a second Hamiltonian cycle in cubic graphs. J. Comput. Syst. Sci. 58 (3): 641-647 (1999)
Andrew Thomason: Hamiltonian cycles and uniquely edge colourable graphs. Ann. Discrete Math. 3: 259-268 (1978)
Preliminary scope of work
Andrew Thomason navrhl elegantní algoritmus pro nalezení druhé Hamiltonovské kružnice v kubickém grafu, čímž podal alternativní důkaz Smithovy věty. Později Adam Krawczyk zkonstruoval příklad grafu, ve kterém Thomasonův algoritmus potřebuje exponenciálně mnoho kroků při spuštění na určitou hranu. Bylo by zajímavé vědět, zda tento algoritmus potřebuje exponenciálně mnoho kroků při spuštění na libovolnou hranu Krawczykova grafu.
Preliminary scope of work in English
Andrew Thomason designed an elegant algorithm for finding a second Hamitonian cycle in a cubic graph. By this he reproved Smith's theorem. Later Adam Krawczyk constructed an example of a graph for which the algorithm requires an exponential number of steps, when started on a specific edge of the graph. It would be interesting to know if the algorithm requires exponential time when started on any edge of the graph.
- assigned and confirmed by the Study Dept.