Fixed-parameter tractability results for feedback set problems in tournaments
From MaRDI portal
Publication:2266940
DOI10.1016/J.JDA.2009.08.001zbMATH Open1191.68349OpenAlexW2165662279MaRDI QIDQ2266940FDOQ2266940
Authors: Michael Dom, Jiong Guo, Falk Hüffner, Anke Truss, Rolf Niedermeier 
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
Recommendations
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Parameterized complexity of directed feedback set problems in tournaments.
- Fixed-parameter complexity of feedback vertex set in bipartite tournaments
- Parameterized and Exact Computation
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- A parameterized algorithm for subset feedback vertex set in tournaments
- An approximation algorithm for feedback vertex sets in tournaments
- Improved approximation algorithm for the feedback set problem in a bipartite tournament
- Linear programming based approximation algorithms for feedback set problems in bipartite tournaments
fixed-parameter tractabilityfeedback arc settournamentfeedback vertex setbipartite tournamentiterative compression
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Kernels: Annotated, Proper and Induced
- Aggregating inconsistent information: ranking and clustering
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Title not available (Why is that?)
- Ranking Tournaments
- Title not available (Why is that?)
- On the hardness of approximating minimum vertex cover
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Improved algorithms for feedback vertex set problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- A fast algorithm for computing longest common subsequences
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Improved Parameterized Upper Bounds for Vertex Cover
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Fast FAST
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Open problems around exact algorithms
- Feedback arc set problem in bipartite tournaments
- Title not available (Why is that?)
- A Min-Max Theorem on Feedback Vertex Sets
- Feedback arc set in bipartite tournaments is NP-complete
- An approximation algorithm for feedback vertex sets in tournaments
- Kernelization Algorithms for d-Hitting Set Problems
- An efficient fixed-parameter algorithm for 3-hitting set
- Improved approximation algorithm for the feedback set problem in a bipartite tournament
- A survey on the linear ordering problem for weighted or unweighted tournaments
- On enumerating all minimal solutions of feedback problems
- On maximal transitive subtournaments
- Algorithms and experiments for parameterized approaches to hard graph problems
- Fixed-Parameter Algorithms for Cluster Vertex Deletion
- Title not available (Why is that?)
- Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
- Iterative Compression and Exact Algorithms
- Improved FPT algorithm for feedback vertex set problem in bipartite tournament
Cited In (34)
- Parameterised algorithms for deletion to classes of DAGs
- A parameterized algorithm for subset feedback vertex set in tournaments
- Conflict free version of covering problems on graphs: classical and parameterized
- Feedback arc set in bipartite tournaments is NP-complete
- Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Improved bounds for minimal feedback vertex sets in tournaments
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Parameterized complexity of directed feedback set problems in tournaments.
- Polynomial kernels for deletion to classes of acyclic digraphs
- Faster exact and parameterized algorithm for feedback vertex set in bipartite tournaments
- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
- Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
- A survey of parameterized algorithms and the complexity of edge modification
- An improved parameterized algorithm for the independent feedback vertex set problem
- Parameterized and Exact Computation
- A quadratic vertex kernel for feedback arc set in bipartite tournaments
- 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
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Kernels for deletion to classes of acyclic digraphs
- Hardness of subgraph and supergraph problems in \(c\)-tournaments
- Brief announcement: Treewidth modulator: emergency exit for DFVS
- Possible winner problems on partial tournaments: a parameterized study
- The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
- Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
- Fixed-parameter complexity of feedback vertex set in bipartite tournaments
- Sub-exponential time parameterized algorithms for graph layout problems on digraphs with bounded independence number
- Algorithms for deletion problems on split graphs
- Comparing and aggregating partial orders with Kendall tau distances
- Tractability of König edge deletion problems
- A multivariate framework for weighted FPT algorithms
This page was built for publication: Fixed-parameter tractability results for feedback set problems in tournaments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2266940)
