Fixed-parameter tractability results for feedback set problems in tournaments
From MaRDI portal
Publication:2266940
DOI10.1016/j.jda.2009.08.001zbMath1191.68349MaRDI QIDQ2266940
Rolf Niedermeier, Jiong Guo, Michael Dom, Falk Hüffner, Anke Truss
Publication date: 26 February 2010
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2009.08.001
tournament; bipartite tournament; feedback vertex set; fixed-parameter tractability; feedback arc set; iterative compression
68Q25: Analysis of algorithms and problem complexity
90C60: Abstract computational complexity for mathematical programming problems
90C27: Combinatorial optimization
Related Items
Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Exploiting a hypergraph model for finding Golomb rulers, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique, A quadratic vertex kernel for feedback arc set in bipartite tournaments, Possible winner problems on partial tournaments: a parameterized study, The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders, A multivariate framework for weighted FPT algorithms, An improved parameterized algorithm for the independent feedback vertex set problem, COMPARING AND AGGREGATING PARTIAL ORDERS WITH KENDALL TAU DISTANCES
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Feedback arc set in bipartite tournaments is NP-complete
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- An efficient fixed-parameter algorithm for 3-hitting set
- Improved algorithms for feedback vertex set problems
- Improved approximation algorithm for the feedback set problem in a bipartite tournament
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- On enumerating all minimal solutions of feedback problems
- Improved FPT algorithm for feedback vertex set problem in bipartite tournament
- Feedback arc set problem in bipartite tournaments
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Open problems around exact algorithms
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- A survey on the linear ordering problem for weighted or unweighted tournaments
- An Approximation Algorithm for Feedback Vertex Sets in Tournaments
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Kernels: Annotated, Proper and Induced
- Iterative Compression and Exact Algorithms
- Kernelization Algorithms for d-Hitting Set Problems
- Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Fast FAST
- A fast algorithm for computing longest common subsequences
- Fixed-Parameter Algorithms for Cluster Vertex Deletion
- Ranking Tournaments
- On maximal transitive subtournaments
- A Min-Max Theorem on Feedback Vertex Sets
- Improved Parameterized Upper Bounds for Vertex Cover
- Aggregating inconsistent information
