# Maximum Matching and a Polyhedron With 0,1-Vertices

• Published in 1964
A matching in a graph $G$ is a subset of edges in $G$ such that no two meet the same node in $G$. The convex polyhedron $C$ is characterised, where the extreme points of $C$ correspond to the matchings in $G$. Where each edge of $G$ carries a real numerical weight, an efficient algorithm is described for finding a matching in $G$ with maximum weight-sum.

### BibTeX entry

@misc{item49,
title = {Maximum Matching and a Polyhedron With 0,1-Vertices},
author = {Jack Edmonds},
url = {http://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125{\_}A1b.pdf},
urldate = {2015-03-07},
abstract = {A matching in a graph {\$}G{\$} is a subset of edges in {\$}G{\$} such that no two meet the same node in {\$}G{\$}. The convex polyhedron {\$}C{\$} is characterised, where the extreme points of {\$}C{\$} correspond to the matchings in {\$}G{\$}. Where each edge of {\$}G{\$} carries a real numerical weight, an efficient algorithm is described for finding a matching in {\$}G{\$} with maximum weight-sum.},
comment = {},
year = 1964,
collections = {}
}