๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Combinatorics of perfect matchings in plane bipartite graphs and application to tilings

โœ Scribed by J.C. Fournier

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
737 KB
Volume
303
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let G be a plane bipartite graph which admits a perfect matching and with distinguished faces called holes. Let MG denote the perfect matchings graph: its vertices are the perfect matchings of G, two of them being joined by an edge, if and only if they di er only on an alternating cycle bounding a face which is not a hole. We solve the following problem: Find a criterion for two perfect matchings of G to belong to the same connected component of M G , and in particular determine in which case M G is connected. The motivation of this work is a result on tilings of Saldanha et al. (Comput. Geom. 14 (1995) 207).

๐Ÿ“œ SIMILAR VOLUMES

Transversal hypergraphs to perfect match
Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
โœ Endre Boros; Khaled Elbassioni; Vladimir Gurvich ๐Ÿ“‚ Article ๐Ÿ“… 2006 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 285 KB

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers