Weighted Bipartite Matching in Matrix Multiplication Time

DOI10.1007/11786986_25zbMath1223.05241OpenAlexW2159896217MaRDI QIDQ3613766

Piotr Sankowski

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_25

zbMATH Keywords

algorithmbipartite graphsinteger weightmaximum weighted matchingsminimum weight bipartite vertex coverminimum weight disjoint pathssingle source shortest paths

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Online algorithms for the maximum \(k\)-colorable subgraph problem ⋮ On polynomially solvable constrained input selections for fixed and switched linear structured systems ⋮ Near Approximation of Maximum Weight Matching through Efficient Weight Reduction ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Unnamed Item

This page was built for publication: Weighted Bipartite Matching in Matrix Multiplication Time