Faster exact and parameterized algorithm for feedback vertex set in tournaments

DOI10.4230/LIPICS.STACS.2016.49MaRDI QIDQ4601901zbMATH OpenFDO

Authors Mithilesh Kumar, Daniel Lokshtanov

Publication date 24 January 2018

Full work available at URL https://arxiv.org/abs/1510.07676

zbMATH Keywords

exact algorithmstournamentsparameterized algorithmsfeedback vertex setgraph partitions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Faster exact and parameterized algorithm for feedback vertex set in bipartite tournaments
• Feedback vertex sets in tournaments
• Feedback vertex sets in tournaments
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• Parameterized algorithms for feedback set problems and their duals in tournaments

Cited in

(17)

• Tractability of König edge deletion problems
• Improved bounds for minimal feedback vertex sets in tournaments
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• Feedback vertex sets in tournaments
• Feedback vertex sets in tournaments
• Kernels for feedback arc set in tournaments
• Tournaments and Semicomplete Digraphs
• Faster exact and parameterized algorithm for feedback vertex set in bipartite tournaments
• Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
• 2-Approximating Feedback Vertex 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)
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
• Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
• Conflict free version of covering problems on graphs: classical and parameterized
• Fast FAST
• A parameterized algorithm for subset feedback vertex set in tournaments
• Hardness of subgraph and supergraph problems in \(c\)-tournaments

This page was built for publication: Faster exact and parameterized algorithm for feedback vertex set in tournaments

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