[EM] Is River O(n^2 log n) worst case?

[Kevin Venzke]

 Hi Kristofer,
    Le jeudi 23 janvier 2020 à 17:19:01 UTC−6, Kristofer Munsterhjelm <km_elmet at t-online.de> a écrit :  >My idea is that if A and B are in the same set, then either A beats
>someone who beats B, or B beats someone who beats A. If it's the former,
>then admitting A>B would mean make B twice defeated, which is not
>allowed. If it's the latter, then admitting A>B would create a cycle,
>which is not allowed either. So, unlike Ranked Pairs, we don't need to
>know which is the case, because either situation implies A>B should not
>be admitted. So a disjoint set structure suffices.

This seems right. Every candidate in a set, except one, has a path of losses back tothe one exception. So no defeat between any of these candidates can be admitted.
I can't speak to the O notation...
>(Here I thought I had found a cloneproof O(n^2) Condorcet method. But I
>found out it's *just* in excess of that, because of that log factor...)
>>... actually, isn't this just Kruskal's algorithm?

It seems similar (if we say there are two edges between each pair of vertices, torepresent the magnitude of the vote on each side) but given that the River graph willbe directed (with a clear root) I wonder if it must be different, or if that is just a cosmeticissue.
Kevin

  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20200124/3cfff11f/attachment.html>