|
This paper shows that the perfect matching algorithm implicitly given in Egerváry's original work is not polynomial in itself. First we show an example with integer weights that requires exponential number of steps. Then anoter example shows that enabling real number weights it is also possible that the algorithms fails to find an optimal solution in finite number of steps.
Bibtex entry:
| AUTHOR | = | {Jüttner, Alp{\'a}r}, |
| TITLE | = | {On the efficiency of Egerváry's perfect matching algorithm}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2004}, |
| NUMBER | = | {TR-2004-13} |