New parameterized algorithms for the edge dominating set problem

Mingyu Xiao, Ton Kloks, Sheung Hung Poon

Research output: Journal PublicationArticlepeer-review

22 Citations (Scopus)

Abstract

An edge dominating set of a graph G=(V,E) is a subset M⊆E of edges in the graph such that each edge in E-M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem, we are given a graph G=(V,E) and an integer k, and we are asked to decide whether G has an edge dominating set of size at most k. In this paper, we show that the parameterized edge dominating set problem can be solved in O*(2.3147k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k3) edges.

Original languageEnglish
Pages (from-to)147-158
Number of pages12
JournalTheoretical Computer Science
Volume511
DOIs
Publication statusPublished - 4 Nov 2013
Externally publishedYes

Keywords

  • Edge dominating set
  • Graph algorithms
  • Kernelization
  • Parameterized algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'New parameterized algorithms for the edge dominating set problem'. Together they form a unique fingerprint.

Cite this