Can I read The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus on EtoBox?

The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus by J Ellis; H Fan; M Fellows is a scholarly article available to read on EtoBox.

What is The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus about?

We describe an algorithm for the dominating set problem with time complexity O((4g + 40) k n 2 ) for graphs of bounded genus g 1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8 k n 2 ) result for planar graphs. Our method is a refinement of the earlier techniques.

Author

J Ellis; H Fan; M Fellows

Publisher

Elsevier Science; Elsevier ; Academic Press; Elsevier BV (ISSN 0196-6774)

Published

2004

Language

EN