A top-down approach to search-trees: Improved algorithmics for 3-hitting set

DOI10.1007/S00453-008-9199-6MaRDI QIDQ848640zbMATH OpenOpenAlexFDO

Authors Henning Fernau

Publication date 4 March 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9199-6

zbMATH Keywords

Hitting setParametrized algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• Parameterized algorithmics for \(d\)-HITTING SET
• Parameterized approximation algorithms for hitting set
• Parameterized Algorithms for Hitting Set: The Weighted Case
• Parameterized algorithms for \(d\)-hitting set: the weighted case
• An efficient fixed-parameter algorithm for 3-hitting set

Cites work

• scientific article; zbMATH DE number 2084262 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• A refined search tree technique for dominating set on planar graphs
• A theory of diagnosis from first principles
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• An efficient fixed-parameter algorithm for 3-hitting set
• Automata, Languages and Programming
• Automated generation of search tree algorithms for hard graphs modification problems
• Call control with \(k\) rejections
• Combinatorial Pattern Matching
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Faster exact algorithms for hard problems: A parameterized point of view
• Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
• Improved Parameterized Upper Bounds for Vertex Cover
• Kernelization Algorithms for d-Hitting Set Problems
• Kernels: Annotated, Proper and Induced
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• New methods for 3-SAT decision and worst-case analysis
• Parameterized Algorithms for Hitting Set: The Weighted Case
• The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting
• Two-Layer Planarization: Improving on Parameterized Algorithmics
• Vertex cover: Further observations and further improvements

Cited in

(22)

• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• A fast branching algorithm for cluster vertex deletion
• Dynamic kernels for hitting sets and set packing
• Speeding up Exact Algorithms With High Probability
• Strong Backdoors for Default Logic
• Parameterized Algorithms for Hitting Set: The Weighted Case
• 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 kernelization algorithm for \(d\)-hitting set
• Kernelization for cycle transversal problems
• Pseudo-kernelization: A branch-then-Reduce approach for FPT problems
• A bounded search tree algorithm for parameterized face cover
• Backdoors to satisfaction
• Faster parameterized algorithm for cluster vertex deletion
• Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
• Parameterizations of hitting set of bundles and inverse scope
• 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
• Tournaments and Semicomplete Digraphs
• Parameterized approximation algorithms for hitting set
• Fixed-parameter tractability results for feedback set problems in tournaments
• A multivariate framework for weighted FPT algorithms
• A parameterized algorithm for bounded-degree vertex deletion

This page was built for publication: A top-down approach to search-trees: Improved algorithmics for 3-hitting set

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