A linear algorithm for a perfect matching in polyomino graphs

DOI10.1016/J.TCS.2017.02.028MaRDI QIDQ528497zbMATH OpenOpenAlexFDO

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

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

Cited in

(5)

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

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)