New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
From MaRDI portal
Publication:2345984
DOI10.1007/s00224-014-9549-5zbMath1328.68090OpenAlexW2141026984MaRDI QIDQ2345984
Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao, Bruno Escoffier
Publication date: 29 May 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-014-9549-5
Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (9)
On approximating (connected) 2-edge dominating set by a tree ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Unnamed Item ⋮ Algorithmic aspects of upper edge domination ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET
Cites Work
- Unnamed Item
- Parameterized edge dominating set in graphs with degree bounded by 3
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- New parameterized algorithms for the edge dominating set problem
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Improved upper bounds for vertex cover
- Approximating edge dominating set in dense graphs
- Parameterized approximation of dominating set problems
- Improved approximation bounds for edge dominating set in dense graphs
- On two techniques of combining branching and treewidth
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Exact algorithms for edge domination
- Approximation hardness of edge dominating set problems
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parameterized Approximation via Fidelity Preserving Transformations
- A Refined Exact Algorithm for Edge Dominating Set
- Enumerate and Measure: Improving Parameter Budget Management
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- The importance of being biased
- Edge Dominating Sets in Graphs
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
This page was built for publication: New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
