Dilworth's theorem establishes a link between a minimal path cover and a maximal antichain in a digraph. A new proof for Dilworth's theorem is given. Moreover an algorithm to find both the path cover and the antichain, as considered in the theorem, is presented.

Additional Metadata
Publisher Erasmus School of Economics (ESE)
Persistent URL hdl.handle.net/1765/23112
Citation
Pijls, W.H.L.M., & Potharst, R.. (2011). Dilworth's Theorem Revisited, an Algorithmic Proof (No. EI 2011-13). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–7). Erasmus School of Economics (ESE). Retrieved from http://hdl.handle.net/1765/23112