Nino Bašić: A linear time algorithm for perfect matching – Part 1

Abstract: 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.