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 algorithmsfeedback vertex setgraph partitionsparameterized algorithmstournaments

Mathematics Subject Classification ID

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

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

(24)

• Tractability of König edge deletion problems
• Improved FPT algorithm for feedback vertex set problem in bipartite tournament
• Kernels for feedback arc set in tournaments
• Tournaments and Semicomplete Digraphs
• Feedback vertex sets in tournaments
• Fast FAST
• Improved bounds for minimal feedback vertex sets in tournaments
• Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
• Faster exact and parameterized algorithm for feedback vertex set in bipartite tournaments
• Feedback vertex sets 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
• 2-Approximating Feedback Vertex Set in Tournaments
• Conflict free version of covering problems on graphs: classical and parameterized
• A parameterized algorithm for subset feedback vertex set in tournaments
• Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
• Hardness of subgraph and supergraph problems in c-tournaments
• First order logic and twin-width in tournaments and dense oriented graphs
• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Hitting meets packing: how hard can it be?
• Subset feedback vertex set in tournaments as fast as without the subset
• Dynamic parameterized feedback problems in tournaments
• Solving subset feedback vertex set in chordal graphs faster than 2ᵏ
• Subset feedback vertex set in tournaments as fast as without the subset

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)