Parameterized algorithms for feedback set problems and their duals in tournaments
From MaRDI portal
Publication:820159
DOI10.1016/J.TCS.2005.10.010zbMATH Open1086.68105OpenAlexW2087066564MaRDI QIDQ820159FDOQ820159
Authors: Venkatesh Raman, Saket Saurabh 
Publication date: 6 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.010
Recommendations
- Parameterized and Exact Computation
- A parameterized algorithm for subset feedback vertex set in tournaments
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Fixed-parameter tractability results for feedback set problems in tournaments
- Parameterized complexity of directed feedback set problems 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
- Linear Programming Based Approximation Algorithms for Feedback Set Problems in Bipartite Tournaments
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- Ranking Tournaments
- On the existence of subexponential parameterized algorithms
- Finding a Minimum Circuit in a Graph
- Approximating minimum feedback sets and multicuts in directed graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterized complexity of finding subgraphs with hereditary properties.
- An efficient fixed-parameter algorithm for 3-hitting set
- Analogs & duals of the MAST problem for sequences & trees
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Girth in digraphs
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Parameterized complexity of directed feedback set problems in tournaments.
Cited In (39)
- Maximum balanced subgraph problem parameterized above lower bound
- 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
- Parameterized algorithms for \(d\)-hitting set: the weighted case
- What's next? Future directions in parameterized complexity
- Parameterizing edge modification problems above lower bounds
- Fixed-parameter algorithms for cluster vertex deletion
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Parameterized complexity of directed feedback set problems in tournaments.
- The Solution Space of Sorting with Recurring Comparison Faults
- Recurring Comparison Faults: Sorting and Finding the Minimum
- Parameterized Eulerian strong component arc deletion problem on tournaments
- Parameterized complexity of Eulerian deletion problems
- Linear kernels and linear-time algorithms for finding large cuts
- The solution space of sorting with recurring comparison faults
- Optimal parallel construction of prescribed tournaments
- An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
- On the parameterized complexity of reconfiguration problems
- Improved parameterized algorithms for the Kemeny aggregation problem
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
- Parameterized and Exact Computation
- Parameterized complexity of Eulerian deletion problems
- 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
- An updated survey on the linear ordering problem for weighted or unweighted tournaments
- Kernels for feedback arc set in tournaments
- Tournaments and Semicomplete Digraphs
- Hardness of subgraph and supergraph problems in \(c\)-tournaments
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Acyclic Digraphs
- A survey on the linear ordering problem for weighted or unweighted tournaments
- Possible winner problems on partial tournaments: a parameterized study
- Voting Procedures, Complexity of
- Packing arc-disjoint cycles in tournaments
- Parameterized complexity of the induced subgraph problem in directed graphs
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Fixed-parameter tractability results for feedback set problems in tournaments
This page was built for publication: Parameterized algorithms for feedback set problems and their duals in tournaments
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820159)
