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

MaRDI QIDQ4607901zbMATH OpenFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(8)

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

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)