A linear time algorithm for perfect matching (Seminar DM)

Iz MaFiRaWiki

A linear time algorithm for perfect matching – Part 1

Nino Bašić

Torek, 2. decembra 2014, od 10h do 12h, Plemljev seminar, Jadranska 19


A linear time algorithm for perfect matching – Part 2

Nino Bašić

Torek, 9. decembra 2014, od 10h do 12h, Plemljev seminar, Jadranska 19


Povzetek: We will study a linear time algorithm by Hansen and Zheng for determining the existence of a Kekulé structure (i.e. a perfect matching) in a given benzenoid. We will prove its correctness and analyse its time complexity.

If time permits, a library for calculations with benzenoids (coded in Python) will also be presented.

Glej tudi/See also

Seminar za diskretno matematiko

Osebna orodja