MJRTY -- A Fast Majority Vote Algorithm. Boyer, R. S., Moore, & Strother, J. In Automated Reasoning, volume 1, of Automated Reasoning Series, pages 105-117. Springer Netherlands, 1991.
doi  abstract   bibtex   
A new algorithm is presented for determining which, if any, of an arbitrary number of candidates has received a majority of the votes cast in an election. The number of comparisons required is at most twice the number of votes. Furthermore, the algorithm uses storage in a way that permits an efficient use of magnetic tape. A Fortran version of the algorithm is exhibited. The Fortran code has been proved correct by a mechanical verification system for Fortran. The system and the proof are discussed.
@incollection{ boyer91,
  abstract = {A new algorithm is presented for determining which, if any, of an arbitrary number of candidates has received a majority of the votes cast in an election. The number of comparisons required is at most twice the number of votes. Furthermore, the algorithm uses storage in a way that permits an efficient use of magnetic tape. A Fortran version of the algorithm is exhibited. The Fortran code has been proved correct by a mechanical verification system for Fortran. The system and the proof are discussed.},
  added-at = {2014-03-20T00:58:05.000+0100},
  author = {Boyer, Robert S. and Moore, J. Strother},
  biburl = {http://www.bibsonomy.org/bibtex/284355a9b520c23b7570caa210a999bd1/ytyoun},
  booktitle = {Automated Reasoning},
  doi = {10.1007/978-94-011-3488-0_5},
  editor = {Boyer, Robert S.},
  interhash = {04136ecc9045bab9af90015e549fc7a2},
  intrahash = {84355a9b520c23b7570caa210a999bd1},
  isbn = {978-94-010-5542-0},
  keywords = {majority},
  language = {English},
  pages = {105-117},
  publisher = {Springer Netherlands},
  series = {Automated Reasoning Series},
  title = {{MJRTY} -- A Fast Majority Vote Algorithm},
  volume = {1},
  year = {1991}
}

Downloads: 0