New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
From MaRDI portal
Publication:2345984
DOI10.1007/s00224-014-9549-5zbMath1328.68090MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
Unnamed Item, EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET, 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, 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, Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
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
