An efficient fixed-parameter algorithm for 3-hitting set
From MaRDI portal
Publication:876698
DOI10.1016/S1570-8667(03)00009-1zbMATH Open1118.68511MaRDI QIDQ876698FDOQ876698
Authors: Rolf Niedermeier, Peter Rossmanith 
Publication date: 26 April 2007
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for NP-hard problems.
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- An improved fixed-parameter algorithm for vertex cover
- Title not available (Why is that?)
- Algorithms for maximum independent sets
- Vertex cover: Further observations and further improvements
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- New Upper Bounds for Maximum Satisfiability
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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 (55)
- 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
- Exact algorithms for finding minimum transversals in rank-3 hypergraphs
- 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
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Parameterized Algorithms for Hitting Set: The Weighted Case
- Parameterized algorithms and kernels for 3-hitting set with parity constraints
- Parameterized algorithms for \(d\)-hitting set: the weighted case
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- 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 kernelization algorithm for \(d\)-hitting set
- An efficient algorithm for 3NF determination
- Temporal vertex cover with a sliding time window
- Parameterized algorithmics for \(d\)-HITTING SET
- On problems without polynomial kernels
- Computing Hitting Set Kernels By AC^0-Circuits
- Title not available (Why is that?)
- The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment
- Call control with \(k\) rejections
- A bounded search tree algorithm for parameterized face cover
- A fixed-parameter algorithm for minimum quartet inconsistency
- On the Minimum Hitting Set of Bundles Problem
- Algorithms for implicit hitting set problems
- Backdoor sets of quantified Boolean formulas
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
- 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
- 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
- On the minimum hitting set of bundles problem
- Parameterized algorithms for feedback set problems and their duals in tournaments
- From causes for database queries to repairs and model-based diagnosis and back
- On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
- Tournaments and Semicomplete Digraphs
- Towards optimal and expressive kernelization for \(d\)-hitting set
- Hardness of subgraph and supergraph problems in \(c\)-tournaments
- Fixed-parameter algorithms for fair hitting set problems
- The minimal hitting set generation problem: algorithms and computation
- Generating Faster Algorithms for d-Path Vertex Cover
- Parameterized approximation algorithms for hitting set
- There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
- An improved upper bound for SAT
- An efficient branch-and-bound solver for hitting set
- 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
- A parameterized algorithm for bounded-degree vertex deletion
- 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)
