A Decomposition Theorem for Maximum Weight Bipartite Matchings

Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung +1

Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N and W be the node count, the largest edge weight and the total weight of…