Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

Details Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

2009-03-26

arxiv.org/abs/0903.4521v3

Computer Science

Data Structures and Algorithms

12 pages, 1 figure, 1 table

Scientific paper

We show that the k-Dominating Set problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j} as a subgraph, for any fixed i, j >= 1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded- degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner.

Affiliated with

Also associated with

No associations

Rating

Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels 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 Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-64338