Maximum Matching and a Polyhedron With 0,1-Vertices

• Published in 1964
• Added on 2015-03-07

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.

Links

• http://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf

Other information

BibTeX entry

@misc{item49,
	key = {item49},
	type = {misc},
	title = {Maximum Matching and a Polyhedron With 0,1-Vertices},
	author = {Jack Edmonds},
	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 = {},
	date_added = {2015-03-07},
	date_published = {1964-10-09},
	urls = {http://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125{\_}A1b.pdf},
	collections = {},
	url = {http://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125{\_}A1b.pdf},
	urldate = {2015-03-07},
	year = 1964
}