Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
DOI10.1016/J.JCSS.2015.08.002zbMATH Open1346.68112OpenAlexW1801860514MaRDI QIDQ896028FDOQ896028
Authors: Christophe Paul, Anthony Perez, Stéphan Thomassé 
Publication date: 11 December 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2015.08.002
Recommendations
- Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem
- Kernel and fast algorithm for dense triplet inconsistency
- Kernel and fast algorithm for dense triplet inconsistency
- Linear Vertex-kernels for Several Dense Ranking r -Constraint Satisfaction Problems
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)
Cites Work
- Title not available (Why is that?)
- Reconstructing the shape of a tree from observed dissimilarity data
- A kernelization algorithm for \(d\)-hitting set
- On problems without polynomial kernels
- Parametrized complexity theory.
- Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
- Graph theory with applications
- Title not available (Why is that?)
- Ranking Tournaments
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Representatives of Subsets
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Kernel bounds for disjoint cycles and disjoint paths
- An improved kernelization for \(P_{2}\)-packing
- Fixed-parameter tractability results for feedback set problems in tournaments
- Cross-composition: a new technique for kernelization lower bounds
- Fast FAST
- Kernels for feedback arc set in tournaments
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Kernelization: new upper and lower bound techniques
- Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem
- Kernel and fast algorithm for dense triplet inconsistency
- New results on optimizing rooted triplets consistency
- On Sets of Consistent Arcs in a Tournament
- Cyclic ordering is NP-complete
- On generating triangle-free graphs
- Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
- Disproof of a conjecture of Erdös and moser on tournaments
- Hardness of fully dense problems
- Linear Vertex-kernels for Several Dense Ranking r -Constraint Satisfaction Problems
Cited In (3)
This page was built for publication: Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896028)
