A linear algorithm for perfect matching in hexagonal systems (Q1313858): Difference between revisions

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.

0 references

zbMATH Keywords

Kekulé system

0 references

hexagonal system

0 references

perfect matching

0 references

linear-time algorithm

0 references

reviewed by

László A. Székely

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q5753988

0 references

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

0 references

Q3812301

0 references

Perfect matchings in hexagonal systems

0 references

Identifiers

zbMATH Open document ID

0789.05083

0 references

DOI

10.1016/0012-365X(93)90294-4

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1313858

@@ Property / author @@
-Mao Lin Zheng
@@ Property / author: Mao Lin Zheng / rank @@
-Normal rank
@@ Property / reviewed by @@
-László A. Székely
@@ Property / reviewed by: László A. Székely / rank @@
-Normal rank
@@ Property / author @@
+Mao Lin Zheng
@@ Property / author: Mao Lin Zheng / rank @@
+Normal rank
@@ Property / reviewed by @@
+László A. Székely
@@ Property / reviewed by: László A. Székely / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q5753988
@@ Property / cites work: Q5753988 / rank @@
+Normal rank
@@ Property / cites work @@
+An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+Q3812301
@@ Property / cites work: Q3812301 / rank @@
+Normal rank
@@ Property / cites work @@
+Perfect matchings in hexagonal systems
@@ Property / cites work: Perfect matchings in hexagonal systems / rank @@
+Normal rank