Parameterized algorithms for feedback set problems and their duals in tournaments
From MaRDI portal
Publication:820159
DOI10.1016/j.tcs.2005.10.010zbMath1086.68105OpenAlexW2087066564MaRDI QIDQ820159
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items (34)
Possible winner problems on partial tournaments: a parameterized study ⋮ Parameterizing edge modification problems above lower bounds ⋮ Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG ⋮ Parameterized complexity of the induced subgraph problem in directed graphs ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Packing arc-disjoint cycles in tournaments ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Recurring Comparison Faults: Sorting and Finding the Minimum ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Hardness of subgraph and supergraph problems in \(c\)-tournaments ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ Parameterized complexity of Eulerian deletion problems ⋮ Kernels for feedback arc set in tournaments ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ \textsc{Max-Cut} parameterized above the Edwards-Erdős bound ⋮ Voting Procedures, Complexity of ⋮ On the parameterized complexity of reconfiguration problems ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Fixed-parameter algorithms for cluster vertex deletion ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ The solution space of sorting with recurring comparison faults ⋮ The Solution Space of Sorting with Recurring Comparison Faults ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Improved Parameterized Algorithms for the Kemeny Aggregation Problem ⋮ Tournaments and Semicomplete Digraphs ⋮ Acyclic Digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An efficient fixed-parameter algorithm for 3-hitting set
- Approximating minimum feedback sets and multicuts in directed graphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- On the existence of subexponential parameterized algorithms
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
- Finding a Minimum Circuit in a Graph
- Girth in digraphs
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Analogs & duals of the MAST problem for sequences & trees
- Parameterized and Exact Computation
- Ranking Tournaments
- Algorithms and Data Structures
This page was built for publication: Parameterized algorithms for feedback set problems and their duals in tournaments
