Kernels for feedback arc set in tournaments

DOI10.1016/j.jcss.2010.10.001zbMath1235.05134OpenAlexW2135418030WikidataQ60488571 ScholiaQ60488571MaRDI QIDQ657916

Serge Gaspers, Saket Saurabh, Anthony Perez, Stéphane Bessy, Fedor V. Fomin, Christophe Paul, Steéphan Thomassé

Publication date: 11 January 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.10.001

zbMATH Keywords

digraphdirected graphtournamentsgraph algorithmsparameterized algorithmskernelizationfeedback arc set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (23)

Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes ⋮ Parameterizing edge modification problems above lower bounds ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders ⋮ Decomposability index of tournaments ⋮ Packing arc-disjoint cycles in tournaments ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ Cluster editing: kernelization based on edge cuts ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ Kernels for packing and covering problems ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Unnamed Item ⋮ The solution space of sorting with recurring comparison faults ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ The Solution Space of Sorting with Recurring Comparison Faults ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES ⋮ Tournaments and Semicomplete Digraphs ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments

Cites Work

• Parameterized algorithms for feedback set problems and their duals in tournaments
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• Voting schemes for which it can be difficult to tell who won the election
• Linear-time modular decomposition of directed graphs
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Fast FAST
• Incompressibility through Colors and IDs
• (Meta) Kernelization
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Ranking Tournaments
• On Sets of Consistent Arcs in a Tournament
• Disproof of a conjecture of Erdös and moser on tournaments
• Optimal ranking of tournaments
• Aggregating inconsistent information
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Kernels for feedback arc set in tournaments