Template-Type: ReDIF-Paper 1.0
Author-Name: Pijls, W.H.L.M.
Author-Name-Last: Pijls
Author-Name-First: Wim
Title: The minimum spanning tree and duality in graphs
Abstract: 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.
Creation-Date: 2013-04-19
File-URL: https://repub.eur.nl/pub/40236/EI2013-14.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI2013-14
Keywords: algorithms, duality
Handle: RePEc:ems:eureir:40236