Group for Research in Decision Analysis

G-91-22

A Linear Algorithm for Perfect Matching in Hexagonal Systems

and

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