Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament

2010/01/01 by Marek Karpiński, Marek Karpinski, Warren Schudy · 1 citation
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Betweenness centrality #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Game Theory and Voting Systems #Mathematics #Rank (graph theory) #Ranking (information retrieval) #Set (abstract data type) #Time complexity #Tournament

paper · doi:10.1007/978-3-642-17517-6_3

crossref issued 2010/01/01 · crossref published 2010/01/01 · crossref published-print 2010/01/01 · openalex publication_date 2010/01/01 · crossref created 2010/12/03 · crossref deposited 2023/06/04 · openalex created_date 2025/10/10 · crossref indexed 2026/06/18 · openalex updated_date 2026/08/04

Citations

• Parameterized Complexity Theory
• Fixed-Parameter Algorithms for Computing Kemeny Scores - Theory and Practice
• Total Ordering Problem
• How to rank with few errors
• Which Problems Have Strongly Exponential Complexity?
• Hardness of fully dense problems
• A Geometric Approach to Betweenness
• Noisy Sorting Without Resampling
• Inconsistencies in a schedule of paired comparisons
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Every Permutation CSP of arity 3 is Approximation Resistant
• Ranking Tournaments
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

Cited by

• Feedback arc set [wikipedia]