Publication

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai
2018
Journal Articles

Abstract

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell's condition is satisfied.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Finding Perfect Matchings in Bipartite Hypergraphs

Chat with Graph Search

Non-planarity of Markoff graphs mod p

The Power of Two Matrices in Spectral Algorithms for Community Recovery

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem