Weighted Bipartite Matching in Matrix Multiplication Time

DOI10.1007/11786986_25MaRDI QIDQ3613766zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Maximum weight bipartite matching in matrix multiplication time
• Experimental and Efficient Algorithms
• Optimum matchings in weighted bipartite graphs
• A scaling algorithm for maximum weight matching in bipartite graphs
• A decomposition theorem for maximum weight bipartite matchings

Cited in

(23)

• Maximum weight bipartite matching in matrix multiplication time
• A heuristic for Dijkstra's algorithm with many targets and its use in weighted matching algorithms
• Online algorithms for the maximum \(k\)-colorable subgraph problem
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• Finding a complete matching with the maximum product on weighted bipartite graphs
• Algebraic algorithms for linear matroid parity problems
• Near approximation of maximum weight matching through efficient weight reduction
• Algorithmic applications of Baur-Strassen's theorem, shortest cycles, diameter, and matchings
• A recurrent algorithm to solve the weighted matching problem
• Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
• scientific article; zbMATH DE number 3902700 (Why is no real title available?)
• scientific article; zbMATH DE number 1104338 (Why is no real title available?)
• scientific article; zbMATH DE number 1487880 (Why is no real title available?)
• scientific article; zbMATH DE number 1877048 (Why is no real title available?)
• Perturbation analysis of maximum-weighted bipartite matchings with low rank data
• scientific article; zbMATH DE number 1405800 (Why is no real title available?)
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
• Optimal Weighted Matchings for Rank-Deficient Sparse Matrices
• Experimental and Efficient Algorithms
• A scaling algorithm for maximum weight matching in bipartite graphs
• A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings
• Algorithms for weighted matching generalizations. I: Bipartite graphs, b-matching, and unweighted f-factors
• On polynomially solvable constrained input selections for fixed and switched linear structured systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613766)