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

DOI10.1002/jgt.20180zbMath1108.05066OpenAlexW4243953177MaRDI QIDQ3419712

Endre Boros, Khaled M. Elbassioni, Vladimir A. Gurvich

Publication date: 7 February 2007

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20180

zbMATH Keywords

blockersgeneration algorithmsmatchable graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (8)

Matching interdiction ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Generating cut conjunctions in graphs and related problems ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Conditional matching preclusion for regular bipartite graphs and their Cartesian product ⋮ Minimum \(k\)-critical bipartite graphs ⋮ Blockers and transversals ⋮ Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Integer Programming and Combinatorial Optimization
• LATIN 2004: Theoretical Informatics

This page was built for publication: Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms