Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
From MaRDI portal
Publication:719315
DOI10.1016/j.tcs.2011.06.018zbMath1225.68096arXiv1010.5881MaRDI QIDQ719315
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.5881
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Partially Polynomial Kernels for Set Cover and Test Cover, Fixed-parameter tractability of satisfying beyond the number of variables, Dual parameterization of weighted coloring, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Alternative parameterizations of \textsc{Metric Dimension}, Parameterized complexity of secluded connectivity problems, Large Independent Sets in Subquartic Planar Graphs, Contraction Blockers for Graphs with Forbidden Induced Paths, The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
Cites Work
- Unnamed Item
- Unnamed Item
- A probabilistic approach to problems parameterized above or below tight bounds
- Vertex cover problem parameterized above and below tight bounds
- Finding odd cycle transversals.
- Total domination of graphs and small transversals of hypergraphs
- A kernelization algorithm for \(d\)-hitting set
- Parameterizing above or below guaranteed values
- On problems without polynomial kernels
- Almost 2-SAT is fixed-parameter tractable
- Covering all cliques of a graph
- Small transversals in hypergraphs
- The colour theorems of Brooks and Gallai extended
- Using nondeterminism to design efficient deterministic algorithms
- Betweenness parameterized above tight lower bound
- Parametrized complexity theory.
- A fixed-parameter algorithm for the directed feedback vertex set problem
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterized and Exact Computation
- Computing and Combinatorics
- SOFSEM 2006: Theory and Practice of Computer Science
