{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T06:25:11Z","timestamp":1771655111368,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642175169","type":"print"},{"value":"9783642175176","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_3","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:13:41Z","timestamp":1291407221000},"page":"3-14","source":"Crossref","is-referenced-by-count":41,"title":["Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"Warren","family":"Schudy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"8","key":"3_CR1","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1016\/j.ic.2007.02.006","volume":"205","author":"N. Ailon","year":"2007","unstructured":"Ailon, N., Alon, N.: Hardness of fully dense problems. Inf. Comput.\u00a0205(8), 1117\u20131129 (2007)","journal-title":"Inf. Comput."},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: Ranking and clustering. Journal of the ACM\u00a055(5), Article No. 23 (2008)","DOI":"10.1145\/1411509.1411513"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1137\/050623905","volume":"20","author":"N. Alon","year":"2006","unstructured":"Alon, N.: Ranking tournaments. SIAM J. Discrete Math.\u00a020(1), 137\u2013142 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-642-02927-1_6","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2009","unstructured":"Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 49\u201358. Springer, Heidelberg (2009)"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00303169","volume":"6","author":"J. Bartholdi III","year":"1989","unstructured":"Bartholdi III, J., Tovey, C., Trick, M.: Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare\u00a06, 157\u2013165 (1989)","journal-title":"Social Choice and Welfare"},{"key":"3_CR6","unstructured":"Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomass\u00e9, S.: Kernels for feedback arc set in tournaments. In: FSTTCS 2009: 29th Foundations of Software Technology and Theoretical Computer Science (2009)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/978-3-540-68880-8_8","volume-title":"Algorithmic Aspects in Information and Management","author":"N. Betzler","year":"2008","unstructured":"Betzler, N., Fellows, M.R., Guo, J., Niedermeier, R., Rosamond, F.A.: Fixed-parameter algorithms for Kemeny scores. In: Fleischer, R., Xu, J. (eds.) AAIM 2008. LNCS, vol.\u00a05034, pp. 60\u201371. Springer, Heidelberg (2008)"},{"key":"#cr-split#-3_CR8.1","unstructured":"Betzler, N., Fellows, M.R., Guo, J., Niedermeier, R., Rosamond, F.A.: How similarity helps to efficiently compute Kemeny rankings. In: AAMAS 2009: 8th International Conference on Autonomous Agents and Multiagent Systems, pp. 657\u2013664 (2009);"},{"key":"#cr-split#-3_CR8.2","doi-asserted-by":"crossref","unstructured":"Journal version in Theoretical Computer Science 410, 4554\u20134570 (2009)","DOI":"10.1016\/j.tcs.2009.08.033"},{"key":"3_CR9","unstructured":"Braverman, M., Mossel, E.: Noisy sorting without resampling. In: Procs. 19th ACM-SIAM SODA, pp. 268\u2013276 (2008)"},{"key":"3_CR10","unstructured":"Bredereck, R.: Fixed-parameter algorithms for computing Kemeny scores\u2014theory and practice. Technical report, Studienarbeit, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Germany (2009) arXiv:1001.4003v1"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548306007887","volume":"16","author":"P. Charbit","year":"2007","unstructured":"Charbit, P., Thomasse, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics, Probability and Computing\u00a016, 1\u20134 (2007)","journal-title":"Combinatorics, Probability and Computing"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guruswami, V., Manokaran, R.: Every Permutation CSP of Arity 3 is Approximation Resistant. In: 24th IEEE CCC (2009)","DOI":"10.1109\/CCC.2009.29"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/S0895480195296221","volume":"11","author":"B. Chor","year":"1998","unstructured":"Chor, B., Sudan, M.: A geometric approach to betweenness. SIAM J. Discrete Math.\u00a011(4), 511\u2013523 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1613\/jair.587","volume":"10","author":"W.W. Cohen","year":"1999","unstructured":"Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. J. Artificial Intelligence Research\u00a010, 243\u2013270 (1999)","journal-title":"J. Artificial Intelligence Research"},{"key":"3_CR15","unstructured":"Conitzer, V.: Computing Slater rankings using similarities among candidates. In: Procs. 21st AAAI, pp. 613\u2013619 (2006)"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Fleischer, L., Rudra, A.: Ordering by weighted number of wins gives a good ranking for weighted tournaments. In: Procs. 17th ACM-SIAM SODA, pp. 776\u2013782 (2006)","DOI":"10.1145\/1109557.1109642"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/11758471_31","volume-title":"Algorithms and Complexity","author":"M. Dom","year":"2006","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Tru\u00df, A.: Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol.\u00a03998, pp. 320\u2013331. Springer, Heidelberg (2006)"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggegation methods for the web. In: Procs. 10th WWW, pp. 613\u2013622 (2001), The NP-hardness proof is in the online-only appendix available from http:\/\/www10.org\/cdrom\/papers\/577\/","DOI":"10.1145\/371920.372165"},{"key":"3_CR19","unstructured":"Feige, U.: Faster fast (feedback arc set in tournaments), arXiv:0911.5094 (2009)"},{"key":"3_CR20","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: Which problems have strongly exponential complexity? J. Computer and System Sciences\u00a063, 512\u2013530 (2001)","journal-title":"J. Computer and System Sciences"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: Procs. Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"3_CR23","unstructured":"Karpinski, M., Schudy, W.: Approximation schemes for the betweenness problem in tournaments and related ranking problems. arXiv:0911.2214 (2009)"},{"key":"3_CR24","first-page":"571","volume":"88","author":"J. Kemeny","year":"1959","unstructured":"Kemeny, J.: Mathematics without numbers. Daedalus\u00a088, 571\u2013591 (1959)","journal-title":"Daedalus"},{"key":"#cr-split#-3_CR25.1","unstructured":"Kemeny, J., Snell, J.: Mathematical models in the social sciences. Blaisdell, New York (1962);"},{"key":"#cr-split#-3_CR25.2","unstructured":"Reprinted by MIT press, Cambridge (1972)"},{"key":"3_CR26","unstructured":"Mathieu, C., Schudy, W.: How to Rank with Few Errors. In: 39th ACM STOC, pp. 95\u2013103 (2009), In Submission, http:\/\/www.cs.brown.edu\/~ws\/papers\/fast_journal.pdf"},{"issue":"1","key":"3_CR27","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0208008","volume":"8","author":"J. Opatrny","year":"1979","unstructured":"Opatrny, J.: Total ordering problems. SIAM J. Comput.\u00a08(1), 111\u2013114 (1979)","journal-title":"SIAM J. Comput."},{"key":"3_CR28","unstructured":"Saurabh, S.: Chromatic coding and universal (hyper-) graph coloring families. In: Parameterized Complexity News, pp. 3\u20134 (June 2009), http:\/\/mrfellows.net\/Newsletters\/2009June_FPT_News.pdf"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/biomet\/48.3-4.303","volume":"48","author":"P. Slater","year":"1961","unstructured":"Slater, P.: Inconsistencies in a schedule of paired comparisons. Biometrika\u00a048, 303\u2013312 (1961)","journal-title":"Biometrika"},{"issue":"1","key":"3_CR30","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1257\/jep.9.1.51","volume":"9","author":"P. Young","year":"1995","unstructured":"Young, P.: Optimal voting rules. The Journal of Economic Perspectives\u00a09(1), 51\u201364 (1995)","journal-title":"The Journal of Economic Perspectives"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,4]],"date-time":"2023-06-04T10:46:19Z","timestamp":1685875579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}