Group for Research in Decision Analysis


A Linear Algorithm for Perfect Matching in Hexagonal Systems


A hexagonal system is a connected plane graph without cut vertices in which each interior face is a regular hexagon. A linear algorithm is proposed to find a perfect matching in a hexagonal system or show that there are none. This improves on the complexity of previous methods.

, 24 pages

This cahier was revised in March 1992