A Decomposition Theorem for Maximum Weight Bipartite Matchings

Simple item page
dc.creatorKao, Ming-Yang
dc.creatorLam, Tak-Wah
dc.creatorSung, Wing-Kin
dc.creatorTing, Hing-Fung
dc.date2000-11-11
dc.date.accessioned2026-07-07T03:16:42Z
dc.date.available2026-07-07T03:16:42Z
dc.descriptionLet 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 G. Let k(x,y) be log(x)/log(x^2/y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O(sqrt(n)W/k(n,W/N))-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G-{u} for all nodes u in O(W) time.
dc.descriptionThe journal version will appear in SIAM Journal on Computing. The conference version appeared in ESA 1999
dc.identifierhttps://arxiv.org/abs/cs/0011015
dc.identifierhttp://arxiv.org/abs/cs/0011015
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30454
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectE1; F2.2
dc.titleA Decomposition Theorem for Maximum Weight Bipartite Matchings
dc.typetext

Files

Collections

arXiv