Subquadratic kernels for implicit 3-hitting set and 3-set packing problems

zbMATH Open1403.68167MaRDI QIDQ4607901FDOQ4607901

Authors: Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi, Stéphan Thomassé 

Publication date: 15 March 2018

Full work available at URL: http://dl.acm.org/citation.cfm?id=3175290

Recommendations

• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
• A Problem Kernelization for Graph Packing
• A Quadratic Kernel for 3-Set Packing
• Kernelization Algorithms for d-Hitting Set Problems
• Triangle packing in (sparse) tournaments: approximation and kernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (8)

• A Quadratic Kernel for 3-Set Packing
• Packing Arc-Disjoint Cycles in Tournaments
• Polyhedral properties of the induced cluster subgraphs
• The maximum independent union of cliques problem: complexity and exact approaches
• Vertex deletion on split graphs: beyond 4-hitting set
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
• Brief announcement: Treewidth modulator: emergency exit for DFVS
• Packing arc-disjoint cycles in tournaments

This page was built for publication: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607901)