A linear algorithm for perfect matching in hexagonal systems
A hexagonal system is a two-connected plane graph in which each interior face is a regular hexagon. Empirical evidence shows that a benzenoid molecule corresponding to the hexagonal system exists if and only if the hexagonal system has a perfect matching (Kekulé system). The paper proposes a linear-time algorithm to find a perfect matching or to show that there is none.
scientific article; zbMATH DE number 500636