Planar graphs and Hamiltonian cycles [1ECTS, MAT03]


Relatore
Carol Zamfirescu - Ghent University

Data e ora
lunedì 1 febbraio 2021 - (recorded lectures)

Referente

Data pubblicazione
10 marzo 2021

Dipartimento
Informatica  

Riassunto


Topics presented in the course include Euler’s polyhedral formula, Kuratowski’s Theorem, the Four Colour Theorem, and the planarity test by Demoucron, Malgrange and Pertuiset.
Moreover, hamiltonian cycles and other important spanning substructures -- such as spanning trees -- will be discussed.
Topics include Grinberg’s hamiltonicity criterion for planar graphs, several heuristics for finding hamiltonian cycles including
Christofides’ algorithm, and Tutte’s Theorem

© 2002 - 2022  Università degli studi di Verona
Via dell'Artigliere 8, 37129 Verona  |  P. I.V.A. 01541040232  |  C. FISCALE 93009870234