CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

New algorithms for maximum weight matching and a decomposition theorem

Chien-Chung Huang (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Telikepalli Kavitha
Mathematics of Operations Research (0364765X). Vol. 42 (2017), 2, p. 411-426.
[Artikel, refereegranskad vetenskaplig]

We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution; thus our algorithm also returns an integral certificate corresponding to the maximum weight matching that was computed. Our algorithm yields a new proof to the total dual integrality of Edmonds' matching polytope and it also gives rise to a decomposition theorem for the maximum weight of a matching in terms of the maximum size of a matching in certain subgraphs. We also consider the maximum weight capacitated b-matching problem in bipartite graphs with nonnegative integral edge weights and show that it can also be decomposed into W unweighted versions of the problem, where W is the largest edge weight. Our second algorithm is competitive with known algorithms when W is small. © 2016 INFORMS.

Nyckelord: Exact algorithms; Maximum weight matching; Total dual integrality



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2017-06-13. Senast ändrad 2017-07-14.
CPL Pubid: 249744

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)

Ämnesområden

Building Futures
Matematik

Chalmers infrastruktur