On kernelization for edge dominating set under structural parameters
From MaRDI portal
Recommendations
Cites work
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- A refined exact algorithm for edge dominating set
- An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
- An improved algorithm for parameterized edge dominating set problem
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Approximating edge dominating set in dense graphs
- Approximation hardness of edge dominating set problems
- Edge dominating set and colorings on graphs with fixed clique-width
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Edge Dominating Sets in Graphs
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Exact algorithms for edge domination
- Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
- Faster parameterized algorithms using linear programming
- Improved approximation bounds for edge dominating set in dense graphs
- Infeasibility of instance compression and succinct PCPs for NP
- Kernelization Lower Bounds by Cross-Composition
- Kernels for edge dominating set: simpler or smaller
- New parameterized algorithms for the edge dominating set problem
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- On problems without polynomial kernels
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- On two techniques of combining branching and treewidth
- Parameterized edge dominating set in graphs with degree bounded by 3
- Paths, flowers and vertex cover
- Polynomial delay algorithm for listing minimal edge dominating sets in graphs
- Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
Cited in
(4)
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)
