A Decomposition Theorem for Maximum Weight Bipartite Matchings

DOI10.1137/S0097539799361208zbMath0989.05091OpenAlexW1981479258MaRDI QIDQ2719128

Wing-Kin Sung, Tak-Wah Lam, Hing-Fung Ting, Ming-Yang Kao

Publication date: 21 June 2001

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539799361208

zbMATH Keywords

graph algorithmweighted bipartite graphmaximum weight matchingall-cavity matching

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Quantum algorithms for matching problems ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Incremental assignment problem ⋮ Weighted approximate parameterized string matching ⋮ Just-in-Time Scheduling with Equal-Size Jobs ⋮ A Filtering Technique for All Pairs Approximate Parameterized String Matching ⋮ Optimal relay assignment and power allocation for cooperative communications ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ Parameterized matching with mismatches ⋮ Reducing rank-maximal to maximum weight matching ⋮ An improved upper bound on the expected regret of UCB-type policies for a matching-selection bandit problem ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Maximum weight bipartite matching in matrix multiplication time ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: A Decomposition Theorem for Maximum Weight Bipartite Matchings