2013-04-19
The minimum spanning tree and duality in graphs
Publication
Publication
Report / Econometric Institute, Erasmus University Rotterdam p. 1- 8
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.
| Additional Metadata | |
|---|---|
| , | |
| Erasmus School of Economics | |
| hdl.handle.net/1765/40236 | |
| Econometric Institute Research Papers | |
| Report / Econometric Institute, Erasmus University Rotterdam | |
| Organisation | Erasmus School of Economics |
|
Pijls, W. (2013). The minimum spanning tree and duality in graphs (No. EI2013-14). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–8). Retrieved from http://hdl.handle.net/1765/40236 |
|
