A Decomposition Theorem for Maximum Weight Bipartite Matchings
<|reference_start|>A Decomposition Theorem for Maximum Weight Bipartite Matchings: 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 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.<|reference_end|>
@article{kao2000a,
    title={A Decomposition Theorem for Maximum Weight Bipartite Matchings},
    author={Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, Hing-Fung Ting},
    journal={arXiv preprint arXiv:cs/0011015},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0011015},
    primaryClass={cs.DS cs.DM}
}