New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
From MaRDI portal
Publication:2345984
Recommendations
- New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
- New parameterized algorithms for the edge dominating set problem
- New Parameterized Algorithms for the Edge Dominating Set Problem
- On approximability of the independent/connected edge dominating set problems
- scientific article; zbMATH DE number 2080196
- A polylogarithmic approximation algorithm for 2-edge-connected dominating set
- Approximation hardness of edge dominating set problems
- Computing and Combinatorics
- On the parameterized complexity of approximating dominating set
- On the Parameterized Complexity of Approximating Dominating Set
Cites work
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- A refined exact algorithm for edge dominating set
- Approximating edge dominating set in dense graphs
- Approximation hardness of edge dominating set problems
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Edge Dominating Sets in Graphs
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Enumerate and measure: improving parameter budget management
- Exact algorithms for edge domination
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved approximation bounds for edge dominating set in dense graphs
- Improved upper bounds for vertex cover
- New parameterized algorithms for the edge dominating set problem
- On two techniques of combining branching and treewidth
- Parameterized approximation of dominating set problems
- Parameterized approximation via fidelity preserving transformations
- Parameterized edge dominating set in graphs with degree bounded by 3
- The importance of being biased
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(14)- On approximating (connected) 2-edge dominating set by a tree
- Algorithmic aspects of upper edge domination
- Improved budgeted connected domination and budgeted edge-vertex domination
- Approximability of the capacitated \(b\)-edge dominating set problem
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Hardness of r-dominating set on graphs of diameter (r + 1)
- New Parameterized Algorithms for the Edge Dominating Set Problem
- New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}
- Edge domination number and the number of minimum edge dominating sets in pseudofractal scale-free web and Sierpiński gasket
- On kernelization for edge dominating set under structural parameters
- On approximating (connected) 2-edge dominating set by a tree
- Upper and lower bounds on approximating weighted mixed domination
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- A sharp upper bound for the edge dominating number of hypergraphs with minimum degree
This page was built for publication: New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345984)
