Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A linear algorithm for a perfect matching in polyomino graphs
Lin Y., Zhang F. Theoretical Computer Science675 82-88,2017.Type:Article
Date Reviewed: Aug 10 2017

Perfect matching in a graph is a set of edges where any pair does not share a common vertex and every vertex of the graph is the endpoint of an edge from that set. From the paper’s introduction: “A polyomino graph is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length 1 (called a cell) and each edge belongs to at least one cell.” It has been an open problem whether finding a perfect matching of a polyomino can be done using an algorithm that runs in linear time in the number of vertices, and this paper offers a solution.

Vertices of the polyomino can be given two colors, white and black, such that every edge connects vertices of different colors. For a subgraph of the polyomino, a difference metric can be defined as the absolute difference in the numbers of white and black vertices of that subgraph. Based on Hall’s theorem, that difference must be zero for a perfect matching to exist.

A key observation used in the paper is that the number of elements in the intersection of a diagonal edge cut with any perfect matching of the graph must equal the difference metric of that diagonal edge cut.

Based on this, and using a labeling scheme of the vertices, the authors have come up with an algorithm that proceeds by considering the diagonal edge cuts near the bottom left corner and using the difference metric to either eliminate forbidden edges or to determine edges that belong to a perfect matching under construction.

In either case, the computation proceeds to the next step on subgraphs formed by that edge cut, eventually terminating with a result that either finds a perfect matching or shows its nonexistence. The authors conclude with a claim that the algorithm is linear because the construction follows a linear process.

Overall, the paper is well written, easy to follow, presents innovative ideas, and contributes an efficient algorithm to this open problem. It will be of much interest to students, researchers, and practitioners.

Reviewer:  Paparao Kavalipati Review #: CR145476 (1710-0671)
Bookmark and Share
  Featured Reviewer  
 
Numerical Algorithms (G.1.0 ... )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms": Date
Performance evaluation of programs related to the real gamma function
Cody W. ACM Transactions on Mathematical Software 17(1): 46-54, 1991. Type: Article
Oct 1 1991
Plotting contour surfaces of a function of three variables
Sewell G. ACM Transactions on Mathematical Software 14(1): 33-41, 1988. Type: Article
Oct 1 1988
Polynomial evaluation with scaling
Hansen E., Patrick M., Wang R. ACM Transactions on Mathematical Software 16(1): 86-93, 1990. Type: Article
May 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy