[EM] finding the beat path winner with just one pass through the ranked pairs

Markus Schulze markus.schulze at alumni.tu-berlin.de
Fri Dec 9 16:07:35 PST 2011


Dear Ross,

the runtime to calculate the strongest path from
every candidate to every other candidate is O(C^3).
However, the runtime to sort O(C^2) pairwise defeats
is already O(C^4). So you cannot get a faster
algorithm by sorting the pairwise defeats.

Markus Schulze




More information about the Election-Methods mailing list