Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments

DOI10.1007/11758471_31zbMath1183.68419OpenAlexW2287816539MaRDI QIDQ3434567

Rolf Niedermeier, Michael Dom, Falk Hüffner, Jiong Guo, Anke Truss

Publication date: 2 May 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11758471_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (15)

Parameterizing edge modification problems above lower bounds ⋮ Feedback arc set in bipartite tournaments is NP-complete ⋮ Improved FPT algorithm for feedback vertex set problem in bipartite tournament ⋮ Kernelization – Preprocessing with a Guarantee ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Kernels for feedback arc set in tournaments ⋮ Voting Procedures, Complexity of ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Chordal deletion is fixed-parameter tractable ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Tournaments and Semicomplete Digraphs

This page was built for publication: Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments