New parameterized algorithms for edge dominating set

Details New parameterized algorithms for edge dominating set New parameterized algorithms for edge dominating set

2011-04-21

arxiv.org/abs/1104.4160v1

Computer Science

Discrete Mathematics

Scientific paper

An edge dominating set of a graph G=(V,E) is a subset M 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.3147^k) time and polynomial space. We show that this problem can be reduced to a quadratic kernel with O(k^3) edges.

Affiliated with

Also associated with

No associations

Rating

New parameterized algorithms for edge dominating set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New parameterized algorithms for edge dominating set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New parameterized algorithms for edge dominating set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-177806