Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem

DOI10.1007/978-3-642-22993-0_45zbMath1343.68119OpenAlexW2290299964MaRDI QIDQ3088066

Anthony Perez, Christophe Paul, Steéphan Thomassé

Publication date: 17 August 2011

Published in: Mathematical Foundations of Computer Science 2011 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22993-0_45

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (7)

Parameterizing edge modification problems above lower bounds ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Kernel and fast algorithm for dense triplet inconsistency ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ A quadratic vertex kernel for feedback arc set in bipartite tournaments ⋮ Kernels for packing and covering problems ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments

This page was built for publication: Conflict Packing Yields Linear Vertex-Kernels for k -FAST, k -dense RTI and a Related Problem