New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set

DOI10.1007/978-3-642-33293-7_5zbMath1329.68137OpenAlexW1847283922MaRDI QIDQ4899238

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

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

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

Related Items (4)

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 ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems

This page was built for publication: New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set