Name
Abstract | ||
|---|---|---|
Given an integer weighted bipartite graph \(\{G,w\}\) we consider the problems of finding all the edges that occur in some minimum weight matching of maximum cardinality and enumerating all the minimum weight perfect matchings. We construct a subgraph \(G_\mathrm{cs}\) of G, which depends on an \(\epsilon \)-optimal solution of the dual linear program associated to the assignment problem on \(\{G,w\}\), that allows us to reduce these problems to their unweighted variants on \(G_\mathrm{cs}\). For instance, starting from scratch we get an algorithm that solves the problem of finding all the edges that occur in some minimum weight perfect matching in time \(O(\sqrt{n}m\log (nW))\), where \(n=|U|\ge |V|\), \(m=|E|\), and \(W=\mathrm{max}\{|w(e)|\, :\, e\in E\}\). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s40590-015-0065-7 | Boletin De La Sociedad Matematica Mexicana |
Keywords | Field | DocType |
Matching,Optimum matching,Assignment problem,Bipartite graph,Weighted bipartite graph,Primary 05C85,Secondary 05C70,68Q25,90C08,90C35 | Integer,Discrete mathematics,Combinatorics,Bipartite graph,Cardinality,Matching (graph theory),Duality (optimization),Assignment problem,Minimum weight,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1403.5606 | 1 | 1405-213X |
Citations | PageRank | References |
1 | 0.36 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos E. Valencia | 1 | 11 | 4.99 |
| Marcos C. Vargas | 2 | 1 | 0.70 |