A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings

DOI10.1016/J.IPL.2022.106286MaRDI QIDQ6337055arXivWikidataFDO

Authors Thorben Tröbst, Vijay V. Vazirani

Publication date 19 March 2020

Mathematics Subject Classification ID

Graph polynomials (05C31) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean functions (06E30)

Abstract: In a recent paper, Beniamini and Nisan gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph $Gsubseteq{K}_{n,n}$ has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary non-negative weight function $w$ on the edges of $K_{n,n}$, consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph $Gsubseteq{K}_{n,n}$ contains one of these minimum weight perfect matchings.

This page was built for publication: A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337055)