An efficient fixed-parameter algorithm for 3-hitting set
From MaRDI portal
Publication:876698
DOI10.1016/S1570-8667(03)00009-1zbMATH Open1118.68511MaRDI QIDQ876698FDOQ876698
Peter Rossmanith, Rolf Niedermeier
Publication date: 26 April 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Some optimal inapproximability results
- Structure preserving reductions among convex optimization problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- An improved fixed-parameter algorithm for vertex cover
- Algorithms for maximum independent sets
- Vertex cover: Further observations and further improvements
- A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
- A general method to speed up fixed-parameter-tractable algorithms
- Finding a Maximum Independent Set
- New Upper Bounds for Maximum Satisfiability
- New worst-case upper bounds for SAT
- Faster exact algorithms for hard problems: A parameterized point of view
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Approximation and special cases of common subtrees and editing distance
Cited In (40)
- Red blue set cover problem on axis-parallel hyperplanes and other objects
- Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
- Dynamic kernels for hitting sets and set packing
- Title not available (Why is that?)
- Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
- Parameterized complexity of \(d\)-hitting set with quotas
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- There Is No 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Parameterized algorithms for \(d\)-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
- A Parameterized Algorithm for Bounded-Degree Vertex Deletion
- An efficient algorithm for 3NF determination
- Temporal vertex cover with a sliding time window
- On problems without polynomial kernels
- 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size
- Computing Hitting Set Kernels By AC^0-Circuits
- Call control with \(k\) rejections
- A bounded search tree algorithm for parameterized face cover
- Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints
- A fixed-parameter algorithm for minimum quartet inconsistency
- A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
- Backdoor sets of quantified Boolean formulas
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- Parameterizations of hitting set of bundles and inverse scope
- Parameterized algorithms for feedback set problems and their duals in tournaments
- From causes for database queries to repairs and model-based diagnosis and back
- Tournaments and Semicomplete Digraphs
- Towards optimal and expressive kernelization for \(d\)-hitting set
- Hardness of subgraph and supergraph problems in \(c\)-tournaments
- Generating Faster Algorithms for d-Path Vertex Cover
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
- An improved upper bound for SAT
- Fixed-parameter tractability results for feedback set problems in tournaments
- Fixed-parameter tractable algorithms for tracking shortest paths
- A multivariate framework for weighted FPT algorithms
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
This page was built for publication: An efficient fixed-parameter algorithm for 3-hitting set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q876698)
