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

linear algorithmperfect matchingpolyomino graphs

Mathematics Subject Classification ID

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

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)

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

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)