A linear algorithm for a perfect matching in polyomino graphs

DOI10.1016/J.TCS.2017.02.028zbMATH Open1369.05193OpenAlexW2594466861MaRDI QIDQ528497FDOQ528497

Authors: Yuqing Lin, Fuji Zhang 

Publication date: 12 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.02.028

zbMATH Keywords

perfect matchinglinear algorithmpolyomino graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Polyominoes (05B50)

Cites Work

• Perfect matchings of polyomino graphs
• The connectivity of \(Z\)-transformation graphs of perfect matchings of polyominoes
• A linear algorithm for perfect matching in hexagonal systems
• A theorem concerning perfect matchings in hexagonal systems
• Perfect matchings in hexagonal systems

Cited In (5)

• Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs
• On degree-based topological indices of random polyomino chains
• The cutting plane method is polynomial for perfect matchings
• Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids
• The Medusa algorithm for polynomial matings

This page was built for publication: A linear algorithm for a perfect matching in polyomino graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528497)