An efficient fixed-parameter algorithm for 3-hitting set
From MaRDI portal
Recommendations
Cites work
- 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
- A linear-time approximation algorithm for the weighted vertex cover problem
- Algorithms for maximum independent sets
- An improved fixed-parameter algorithm for vertex cover
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Approximation algorithms for NP-hard problems.
- Approximation and special cases of common subtrees and editing distance
- Faster exact algorithms for hard problems: A parameterized point of view
- Finding a Maximum Independent Set
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1304341 (Why is no real title available?)
- scientific article; zbMATH DE number 1305487 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1522934 (Why is no real title available?)
- scientific article; zbMATH DE number 1834643 (Why is no real title available?)
- scientific article; zbMATH DE number 815575 (Why is no real title available?)
- New Upper Bounds for Maximum Satisfiability
- New worst-case upper bounds for SAT
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Some optimal inapproximability results
- Structure preserving reductions among convex optimization problems
- Vertex cover: Further observations and further improvements
Cited in
(62)- A bounded search tree algorithm for parameterized face cover
- On problems without polynomial kernels
- On the minimum hitting set of bundles problem
- Backdoor sets of quantified Boolean formulas
- Multiple hypernode hitting sets and smallest two-cores with targets
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- Call control with \(k\) rejections
- A fixed-parameter algorithm for minimum quartet inconsistency
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Temporal vertex cover with a sliding time window
- Dynamic kernels for hitting sets and set packing
- Optimal-size problem kernels for d-Hitting Set in linear time and space
- Fixed-parameter tractable algorithms for tracking shortest paths
- Fixed-parameter tractability results for feedback set problems in tournaments
- Parameterizations of hitting set of bundles and inverse scope
- A multivariate framework for weighted FPT algorithms
- From causes for database queries to repairs and model-based diagnosis and back
- A parameterized algorithm for bounded-degree vertex deletion
- There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration
- Parameterized approximation algorithms for hitting set
- Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- Parameterized algorithms and kernels for 3-hitting set with parity constraints
- The minimal hitting set generation problem: algorithms and computation
- Parameterized algorithmics for d-HITTING SET
- Tournaments and Semicomplete Digraphs
- Computing Hitting Set Kernels By AC^0-Circuits
- THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
- Parameterized Algorithms for Hitting Set: The Weighted Case
- On the Minimum Hitting Set of Bundles Problem
- Sparse solutions of sparse linear systems: fixed-parameter tractability and an application of complex group testing
- scientific article; zbMATH DE number 2040676 (Why is no real title available?)
- Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
- Exact algorithms for finding minimum transversals in rank-3 hypergraphs
- Towards optimal and expressive kernelization for \(d\)-hitting set
- scientific article; zbMATH DE number 7559382 (Why is no real title available?)
- 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
- The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment
- Algorithms for implicit hitting set problems
- An efficient algorithm for 3NF determination
- On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
- 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
- Hardness of subgraph and supergraph problems in c-tournaments
- Generating Faster Algorithms for d-Path Vertex Cover
- An efficient branch-and-bound solver for hitting set
- Red blue set cover problem on axis-parallel hyperplanes and other objects
- Fixed-parameter algorithms for fair hitting set problems
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Faster parameterized algorithms for variants of \textsc{3-hitting set}
- Subset feedback vertex set in tournaments as fast as without the subset
- A polynomial kernel for deletion to the scattered class of cliques and trees
- Subset feedback vertex set in tournaments as fast as without the subset
- Parameterized complexity of generalizations of edge dominating set
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Parameterized algorithms for feedback set problems and their duals in tournaments
- An improved upper bound for SAT
- Parameterized complexity of d-hitting set with quotas
- A top-down approach to search-trees: Improved algorithmics for 3-hitting set
- Parameterized algorithms for d-hitting set: the weighted case
- A kernelization algorithm for \(d\)-hitting set
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)
