New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}

DOI10.1007/978-3-642-33293-7_5MaRDI QIDQ4899238zbMATH OpenOpenAlexFDO

Authors Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, Mingyu Xiao

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_5

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
• New parameterized algorithms for the edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem
• An improved algorithm for parameterized edge dominating set problem

Cited in

(10)

• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Approximability of the capacitated \(b\)-edge dominating set problem
• Hardness of r-dominating set on graphs of diameter (r + 1)
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Parameterized edge dominating set in graphs with degree bounded by 3
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• On the max min vertex cover problem
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• Parameterized complexity of generalizations of edge dominating set

This page was built for publication: New results on polynomial inapproximability and fixed parameter approximability of \textsc{Edge Dominating Set}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899238)