On kernelization for edge dominating set under structural parameters
From MaRDI portal
Publication:5090486
DOI10.4230/LIPICS.STACS.2019.36MaRDI QIDQ5090486FDOQ5090486
Authors: Eva-Maria C. Hols, Stefan Kratsch 
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1901.03582
Recommendations
Cites Work
- On problems without polynomial kernels
- On two techniques of combining branching and treewidth
- Kernelization Lower Bounds by Cross-Composition
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Infeasibility of instance compression and succinct PCPs for NP
- Edge Dominating Sets in Graphs
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- New parameterized algorithms for the edge dominating set problem
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Faster parameterized algorithms using linear programming
- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- Paths, flowers and vertex cover
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
- Parameterized edge dominating set in graphs with degree bounded by 3
- Improved approximation bounds for edge dominating set in dense graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Edge dominating set and colorings on graphs with fixed clique-width
- Exact algorithms for edge domination
- A refined exact algorithm for edge dominating set
- Kernels for edge dominating set: simpler or smaller
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Approximation hardness of edge dominating set problems
- Approximating edge dominating set in dense graphs
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- An improved algorithm for parameterized edge dominating set problem
- An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
Cited In (3)
This page was built for publication: On kernelization for edge dominating set under structural parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090486)
