A top-down approach to search-trees: Improved algorithmics for 3-hitting set
From MaRDI portal
Publication:848640
DOI10.1007/s00453-008-9199-6zbMath1184.68598MaRDI QIDQ848640
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
Related Items
3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size, Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing, Kernelization for cycle transversal problems, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, A kernelization algorithm for \(d\)-hitting set, A bounded search tree algorithm for parameterized face cover, The union of minimal hitting sets: parameterized combinatorial bounds and counting, Fixed-parameter tractability results for feedback set problems in tournaments, Parameterizations of hitting set of bundles and inverse scope, Sparse Solutions of Sparse Linear Systems: Fixed-Parameter Tractability and an Application of Complex Group Testing, Backdoors to Satisfaction, Speeding up Exact Algorithms With High Probability
Cites Work
- Unnamed Item
- Unnamed Item
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- An efficient fixed-parameter algorithm for 3-hitting set
- A theory of diagnosis from first principles
- Call control with \(k\) rejections
- Automated generation of search tree algorithms for hard graphs modification problems
- New methods for 3-SAT decision and worst-case analysis
- A refined search tree technique for dominating set on planar graphs
- Vertex Cover: Further Observations and Further Improvements
- Two-Layer Planarization: Improving on Parameterized Algorithmics
- Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
- Parameterized Algorithms for Hitting Set: The Weighted Case
- Kernels: Annotated, Proper and Induced
- A new multilayered PCP and the hardness of hypergraph vertex cover
- The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting
- Kernelization Algorithms for d-Hitting Set Problems
- Exact algorithms for finding minimum transversals in rank-3 hypergraphs
- Combinatorial Pattern Matching
- Automata, Languages and Programming
- Improved Parameterized Upper Bounds for Vertex Cover
- Faster exact algorithms for hard problems: A parameterized point of view