### Skapa referens, olika format (klipp och klistra)

**Harvard**

Huang, C. och Kavitha, T. (2017) *New algorithms for maximum weight matching and a decomposition theorem*.

** BibTeX **

@article{

Huang2017,

author={Huang, Chien-Chung and Kavitha, Telikepalli},

title={New algorithms for maximum weight matching and a decomposition theorem},

journal={Mathematics of Operations Research},

issn={0364765X},

volume={42},

issue={2},

pages={411-426},

abstract={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.},

year={2017},

keywords={Exact algorithms; Maximum weight matching; Total dual integrality},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 249744

A1 Huang, Chien-Chung

A1 Kavitha, Telikepalli

T1 New algorithms for maximum weight matching and a decomposition theorem

YR 2017

JF Mathematics of Operations Research

SN 0364765X

VO 42

IS 2

SP 411

OP 426

AB 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.

LA eng

DO 10.1287/moor.2016.0806

LK http://dx.doi.org/10.1287/moor.2016.0806

OL 30