Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique

DOI10.1016/J.JCSS.2015.08.002MaRDI QIDQ896028zbMATHOpenAlexFDO

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

zbMATH Keywords

fixed-parameter algorithmskernelization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

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

Cites work

• scientific article; zbMATH DE number 5485441 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A kernelization algorithm for \(d\)-hitting set
• An improved kernelization for \(P_{2}\)-packing
• Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem
• Cross-composition: a new technique for kernelization lower bounds
• Cyclic ordering is NP-complete
• Disproof of a conjecture of Erdös and moser on tournaments
• Fast FAST
• Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
• Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem
• Fixed-parameter tractability results for feedback set problems in tournaments
• Graph theory with applications
• Hardness of fully dense problems
• Kernel and fast algorithm for dense triplet inconsistency
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization: new upper and lower bound techniques
• Kernels for feedback arc set in tournaments
• Linear Vertex-kernels for Several Dense Ranking r -Constraint Satisfaction Problems
• New results on optimizing rooted triplets consistency
• On Representatives of Subsets
• On Sets of Consistent Arcs in a Tournament
• On generating triangle-free graphs
• On problems without polynomial kernels
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parametrized complexity theory.
• Ranking Tournaments
• Reconstructing the shape of a tree from observed dissimilarity data
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

Cited in

(2)

• Kernel and fast algorithm for dense triplet inconsistency
• Conflict packing yields linear vertex-kernels for \(k\)-FAST, \(k\)-dense RTI and a related problem

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)