Kernels for feedback arc set in tournaments

DOI10.1016/J.JCSS.2010.10.001MaRDI QIDQ657916zbMATHOpenAlexDBLPWikidataFDO

Authors Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, Sté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

graph algorithmsdigraphdirected graphtournamentsfeedback arc setkernelizationparameterized algorithms

Mathematics Subject Classification ID

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

Recommendations

• Kernels for feedback arc set in tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• A polynomial kernel for Feedback Arc Set on bipartite tournaments
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3167398 (Why is no real title available?)
• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 1288298 (Why is no real title available?)
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• scientific article; zbMATH DE number 3329639 (Why is no real title available?)
• scientific article; zbMATH DE number 3405712 (Why is no real title available?)
• (Meta) Kernelization
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• A kernelization algorithm for \(d\)-hitting set
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Aggregating inconsistent information
• Deterministic pivoting algorithms for constrained ranking and clustering problems
• Disproof of a conjecture of Erdös and moser on tournaments
• Fast FAST
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Incompressibility through Colors and IDs
• Linear-time modular decomposition of directed graphs
• On Sets of Consistent Arcs in a Tournament
• On problems without polynomial kernels
• Optimal ranking of tournaments
• Ordering by weighted number of wins gives a good ranking for weighted tournaments
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Ranking Tournaments
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(27)

• The solution space of sorting with recurring comparison faults
• The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
• Comparing and aggregating partial orders with Kendall tau distances
• Kernel and fast algorithm for dense triplet inconsistency
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• Editing graphs into few cliques: complexity, approximation, and kernelization schemes
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• Packing arc-disjoint cycles in tournaments
• Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem
• Kernels for packing and covering problems
• 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
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Kernels for feedback arc set in tournaments
• Tournaments and Semicomplete Digraphs
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
• The solution space of sorting with recurring comparison faults
• A survey of parameterized algorithms and the complexity of edge modification
• Decomposability index of tournaments
• Fast FAST
• Locally Semicomplete Digraphs and Generalizations
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• A polynomial kernel for Feedback Arc Set on bipartite tournaments
• Cluster editing: kernelization based on edge cuts

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657916)