Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
From MaRDI portal
Publication:3060716
DOI10.1007/978-3-642-17517-6_3zbMath1310.68272arXiv1006.4396WikidataQ57568005 ScholiaQ57568005MaRDI QIDQ3060716
Warren Schudy, Marek Karpinski
Publication date: 9 December 2010
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1006.4396
fixed parameter tractability; Kemeny rank aggregation; betweenness tournament; feedback arc set tournament
Related Items
Unnamed Item, Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number, Packing Arc-Disjoint Cycles in Tournaments, Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number, Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index), Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, History-dependent scheduling: models and algorithms for scheduling with general precedence and sequence dependence, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Kernel and fast algorithm for dense triplet inconsistency, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization, Kernels for feedback arc set in tournaments, Cluster editing with locally bounded modifications, Exact localisations of feedback sets, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, Parameterizing edge modification problems above lower bounds, Exploring the median of permutations problem, Cluster editing: kernelization based on edge cuts, On the hardness of maximum rank aggregation problems, A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs, Space reduction constraints for the median of permutations problem, Automedian sets of permutations: direct sum and shuffle, A quadratic vertex kernel for feedback arc set in bipartite tournaments, On width measures and topological problems on semi-complete digraphs, On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments, Packing arc-disjoint cycles in tournaments, Medians of Permutations: Building Constraints, Studies in Computational Aspects of Voting, Ranking and Drawing in Subexponential Time, Cluster Editing: Kernelization Based on Edge Cuts, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
