Beatpath: Difference between revisions
m
clean up (AWB), typos fixed: the the → the
imported>DCary m (Updated link to [http://en.wikipedia.org/wiki/Preorder#Constructions natural partial order generated from that preorder] in order to reflect reorganization of that Wikipedia article) |
Psephomancy (talk | contribs) m (clean up (AWB), typos fixed: the the → the) |
||
Line 3:
In an election, a '''beatpath''' is a sequence of candidates such that each candidate in the sequence beats the next one in a pair-wise contest.
Beatpaths can be used to describe the [[Condorcet paradox]], the [[Schulze method]], and the [[Schwartz set]]. The related concept of a [[#Beat-or-tie_path
Line 35:
==Cycles==
A '''cycle''' is a beatpath that starts and ends at
Two candidates X and Y are '''in a cycle''' when there is a cycle C(0),...,C(n) with X=C(i) and Y=C(j) for some i and j, i ≠ j.
Line 104:
===Examples===
* [[Beatpath examples 3
* [[Beatpath example 12
Line 124:
A version of the [http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm Floyd-Warshall algorithm] can be used to identify the candidates in the maximal elements of the beatpath order or the beat-or-tie order. The Floyd-Warshall algorithm runs in Θ(N<sup>3</sup>) time.
Here are [[Maximal elements algorithms
==See also==
* [[Beatpath examples 3
* [[Beatpath example 12
* [[Maximal elements algorithms
* [[Schwartz set]]
* [[Smith set]]
| |||