A LINEAR ALGORITHM FOR PERFECT MATCHING IN HEXAGONAL SYSTEMS

Authors
HANSEN P ZHENG ML
Citation
P. Hansen et Ml. Zheng, A LINEAR ALGORITHM FOR PERFECT MATCHING IN HEXAGONAL SYSTEMS, Discrete mathematics, 122(1-3), 1993, pp. 179-196
Citations number
9
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Discrete mathematics → ACNP
ISSN journal
0012365X
Volume
122
Issue
1-3
Year of publication
1993
Pages
179 - 196
Database
ISI
SICI code
0012-365X(1993)122:1-3<179:ALAFPM>2.0.ZU;2-5
Abstract
A hexagonal system is a connected plane graph without cut vertices in which each interior face is a regular hexagon. A linear algorithm is p roposed to find a perfect matching in a hexagonal system or show that there are none. This improves on the complexity of previous methods.