Groupe d’études et de recherche en analyse des décisions

G-91-22

A Linear Algorithm for Perfect Matching in Hexagonal Systems

et

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

Ce cahier a été révisé en mars 1992