Coordinatized Kernels and Catalytic Reductions: Improved FPT Algorithms for Max Leaf Spanning Tree and Other Problems.

Michael R. Fellows, Catherine McCartin and Frances A. Rosamond

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


We describe some new, simple and apparently general methods for designing FPT algorithms, and illustrate how these can be used to obtain a significantly improved FPT algorithm for the Maximum Leaf Spanning Tree problem. We sketch how the methods can be applied to a number of other well-known problems, including the parametric dual of Dominating Set (also known as Nonblocker), Matrix Domination, Dominating Set for Line Graphs and Feedback Vertex Set for Undirected Graphs. The main payoffs of these new methods are in improved functions f(k) in the FPT running times, and in general systematic approaches that seem to apply to a wide variety of problems.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems