Kernelization Algorithms for d-Hitting Set Problems

DOI10.1007/978-3-540-73951-7_38MaRDI QIDQ3603547zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73951-7_38

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• A kernelization algorithm for \(d\)-hitting set
• Parameterized and Exact Computation
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Linear kernelizations for restricted 3-Hitting Set problems
• Towards optimal and expressive kernelization for \(d\)-hitting set

Cited in

(41)

• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
• Solving min ones 2-SAT as fast as vertex cover
• Dynamic kernels for hitting sets and set packing
• A parameterized algorithm for subset feedback vertex set in tournaments
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Parameterized complexity of d-hitting set with quotas
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• An efficient fixed-parameter algorithm for 3-hitting set
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• Multiple hypernode hitting sets and smallest two-cores with targets
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• A shortcut to (sun)flowers: kernels in logarithmic space or linear time
• A kernelization algorithm for \(d\)-hitting set
• Fixed-parameter algorithms for cluster vertex deletion
• Parameterized and Exact Computation
• Linear kernelizations for restricted 3-Hitting Set problems
• Two edge modification problems without polynomial kernels
• Computing Hitting Set Kernels By AC^0-Circuits
• Pseudo-kernelization: A branch-then-Reduce approach for FPT problems
• Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
• Even faster algorithm for set splitting!
• Backdoor sets of quantified Boolean formulas
• 3-\textsc{hitting set} on bounded degree hypergraphs: upper and lower bounds on the kernel size
• Fixed-Parameter Algorithms for Cluster Vertex Deletion
• Two edge modification problems without polynomial kernels
• An improved kernelization algorithm for \(r\)-set packing
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Kernelizations for Parameterized Counting Problems
• Hitting and covering partially
• 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Exploring the kernelization borders for hitting cycles
• Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
• Dynamic kernels for hitting sets and set packing
• On generating triangle-free graphs
• A Problem Kernelization for Graph Packing
• There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
• Fixed-parameter tractability results for feedback set problems in tournaments

This page was built for publication: Kernelization Algorithms for d-Hitting Set Problems

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