Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments

DOI10.1007/11758471_31zbMath1183.68419MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C20: Directed graphs (digraphs), tournaments

Related Items

Voting Procedures, Complexity of, A survey of the algorithmic aspects of modular decomposition, Kernels for feedback arc set in tournaments, Feedback arc set in bipartite tournaments is NP-complete, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, 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, Parameterizing edge modification problems above lower bounds, Improved FPT algorithm for feedback vertex set problem in bipartite tournament, A survey on the linear ordering problem for weighted or unweighted tournaments, Kernelization – Preprocessing with a Guarantee, Tournaments and Semicomplete Digraphs, Iterative Compression for Exactly Solving NP-Hard Minimization Problems