The minimum spanning tree and duality in graphs

Several algorithms for the minimum spanning tree are known. The Blue-red algorithm is a generic algorithm in this field. A new proof for this algorithm is presented, based upon the duality of circuits and cuts in a graph. The Blue-red algorithm is genetic, because the other algorithms can be regarded as special instances. This is shown using the same duality.

MoreLess

Year of publication:	2013-04-19
Authors:	Pijls, Pijls, W.H.L.M.
Institutions:	Faculteit der Economische Wetenschappen, Erasmus Universiteit Rotterdam
Subject:	algorithms \| duality

More details

Extent:	application/pdf
Series:	Econometric Institute Research Papers. - ISSN 1566-7294.
Type of publication:	Book / Working Paper
Notes:	The text is part of a series RePEc:ems:eureir Number EI2013-14
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010731650