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.4396OpenAlexW2124900884WikidataQ57568005 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 tractabilityKemeny rank aggregationbetweenness tournamentfeedback arc set tournament
Related Items (31)
Parameterizing edge modification problems above lower bounds ⋮ Studies in Computational Aspects of Voting ⋮ 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 ⋮ Packing arc-disjoint cycles in tournaments ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Space reduction constraints for the median of permutations problem ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number ⋮ Exploring the median of permutations problem ⋮ Automedian sets of permutations: direct sum and shuffle ⋮ Kernels for feedback arc set in tournaments ⋮ Ranking and Drawing in Subexponential Time ⋮ A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization ⋮ Cluster editing: kernelization based on edge cuts ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ On the hardness of maximum rank aggregation problems ⋮ Cluster editing with locally bounded modifications ⋮ Unnamed Item ⋮ Exact localisations of feedback sets ⋮ Cluster Editing: Kernelization Based on Edge Cuts ⋮ Medians of Permutations: Building Constraints ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems ⋮ Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number ⋮ Packing Arc-Disjoint Cycles in 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 ⋮ Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index)
This page was built for publication: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
