Kernels for feedback arc set in tournaments

DOI10.1016/J.JCSS.2010.10.001zbMATH Open1235.05134DBLPjournals/jcss/BessyFGPPST11OpenAlexW2135418030WikidataQ60488571 ScholiaQ60488571MaRDI QIDQ657916FDOQ657916

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

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

zbMATH Keywords

graph algorithmsdigraphdirected graphtournamentsfeedback arc setkernelizationparameterized algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (28)

• Kernel and fast algorithm for dense triplet inconsistency
• Kernels for feedback arc set in tournaments
• Cluster editing: kernelization based on edge cuts
• Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
• Parameterizing edge modification problems above lower bounds
• Decomposability index of tournaments
• Fast FAST
• The Solution Space of Sorting with Recurring Comparison Faults
• Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes
• On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• A polynomial kernel for Feedback Arc Set on bipartite tournaments
• Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem
• Packing Arc-Disjoint Cycles in Tournaments
• 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
• A survey of parameterized algorithms and the complexity of edge modification
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Tournaments and Semicomplete Digraphs
• Efficient algorithms for measuring the funnel-likeness of DAGs
• The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
• Locally Semicomplete Digraphs and Generalizations
• Comparing and aggregating partial orders with Kendall tau distances
• Packing arc-disjoint cycles in tournaments
• Kernels for packing and covering problems
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• Title not available (Why is that?)

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)