id: 02086260
dt: a
an: 02086260
au: Alber, Jochen; Niedermeier, Rolf
ti: Improved tree decomposition based algorithms for domination-like problems.
so: Rajsbaum, Sergio (ed.), LATIN 2002: Theoretical informatics. 5th Latin
    American symposium, Cancun, Mexico, April 3‒6, 2002. Proceedings.
    Berlin: Springer (ISBN 3-540-43400-3). Lect. Notes Comput. Sci. 2286,
    613-627 (2002).
py: 2002
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: http://link.springer.de/link/service/series/0558/bibs/2286/22860613.htm
ab: Summary: We present an improved dynamic programming strategy for DOMINATING
    SET and related problems on graphs that are given together with a tree
    decomposition of width $k$. We obtain an $O(4^k n)$ algorithm for
    DOMINATING SET, where $n$ is the number of nodes of the tree
    decomposition. This result improves the previously best known algorithm
    of Telle and Proskurowski running in time $O(9^k n)$. The key to our
    result is an argument on a certain “monotonicity” in the table
    updating process during dynamic programming. Moreover, various other
    domination-like problems as discussed by Telle and Proskurowski are
    treated with our technique. We gain improvements on the base of the
    exponential term in the running time ranging between 55\% and 68\% in
    most of these cases. These results mean significant breakthroughs
    concerning practical implementations.
rv: