Interesting Esoterica

Maximum Matching and a Polyhedron With 0,1-Vertices

by Jack Edmonds
  • Published in 1964
  • Added on
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


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 = {}
}