Kernels for feedback arc set in tournaments

DOI10.4230/LIPICS.FSTTCS.2009.2305MaRDI QIDQ2920111zbMATH OpenOpenAlexFDO

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

Publication date 24 October 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_f112.html

zbMATH Keywords

kernelsparameterized complexitytournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cited in

(13)

• Cluster editing: kernelization based on edge cuts
• Kernelization: new upper and lower bound techniques
• Fast FAST
• A polynomial kernel for Feedback Arc Set on bipartite tournaments
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• A quadratic vertex kernel for feedback arc set in bipartite tournaments
• A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
• A survey of the algorithmic aspects of modular decomposition
• Kernels for feedback arc set in tournaments
• All feedback arc sets of a random Turán tournament have \(\lfloor{n}/{k}\rfloor-{k}+1\) disjoint \({k}\)-cliques (and this is tight)
• A quadratic vertex kernel for feedback arc set in bipartite tournaments

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 Q2920111)