Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms | Zendy

Boros Endre | Zendy; Elbassioni Khaled | Zendy; Gurvich Vladimir | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

Author(s) -

Boros Endre,

Elbassioni Khaled,

Gurvich Vladimir

Publication year - 2006

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.20180

Subject(s) - combinatorics , bipartite graph , mathematics , strong perfect graph theorem , complete bipartite graph , blossom algorithm , discrete mathematics , perfect graph theorem , matching (statistics) , line graph , cograph , foster graph , perfect graph , pathwidth , graph , voltage graph , statistics

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 of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G . We also provide generation algorithms for other related problems, including d ‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research