A linear algorithm for perfect matching in hexagonal systems
type: Item
instance of: scholarly article
title: A linear algorithm for perfect matching in hexagonal systems
zbMATH Open document ID: 0789.05083
DOI: 10.1016/0012-365X(93)90294-4
author: Pierre Hansen
author: Maolin Zheng
published in: Discrete Mathematics
publication date: 1994-03-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 92E10
zbMATH DE Number: 500636
zbMATH Keywords: Kekulé system
zbMATH Keywords: hexagonal system
zbMATH Keywords: perfect matching
zbMATH Keywords: linear-time algorithm
reviewed by: László A. Székely
MaRDI profile type: Publication
cites work: Q5753988
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Q3812301
cites work: Perfect matchings in hexagonal systems
description: scientific article; zbMATH DE number 500636