A Real Polynomial for Bipartite Graph Minimum Weight Perfect Matchings

DOI10.1016/J.IPL.2022.106286arXiv2003.08917WikidataQ114167077 ScholiaQ114167077MaRDI QIDQ6337055FDOQ6337055

Authors: Thorben Tröbst, Vijay V. Vazirani 

Publication date: 19 March 2020

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.

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)

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)