Thu, 21 Aug 2008 15:04:49 BST CiteULike: AbnerCYH's Arnborg http://www.citeulike.org/user/AbnerCYH/author/Arnborg CiteULike.org en-gb Copyright © 2004-2008 citeulike.org http://www.citeulike.org/user/AbnerCYH/article/1260968 <i>SIAM Journal on Algebraic and Discrete Methods, Vol. 8, No. 2. (1987), pp. 277-284.</i> Complexity of Finding Embeddings in a $k$-Tree Stefan Arnborg Derek Corneil Andrzej Proskurowski SIAM Journal on Algebraic and Discrete Methods, Vol. 8, No. 2. (1987), pp. 277-284. 2007-04-27T18:34:38-00:00 1987 SIAM Journal on Algebraic and Discrete Methods 8 2 277 284 SIAM algebra algorithms graph http://www.citeulike.org/user/AbnerCYH/article/1723905 <i>Discrete Applied Mathematics, Vol. 23, No. 1. (April 1989), pp. 11-24.</i><br /><br />We present and illustrate by a sequence of examples an algorithm paradigm for solving NP- hard problems on graphs restricted to partial graphs of k-trees and given with an embedding in a k-tree. Such algorithms, linear in the size of the graph but exponential or superexponential in k, exist for most NP-hard problems that have linear time algorithms for trees. The examples used are optimization problems involving independent sets, dominating sets, graph coloring, Hamiltonian circuits, network reliability and minimum vertex deletion forbidden subgraphs. The results generalize previous results for series-parallel graphs, bandwidth-constrained graphs, and non- serial dynamic programming. Linear time algorithms for NP-hard problems restricted to partial k-trees Stefan Arnborg Andrzej Proskurowski doi:10.1016/0166-218X(89)90031-0 Discrete Applied Mathematics, Vol. 23, No. 1. (April 1989), pp. 11-24. 2007-10-03T12:34:55-00:00 1989 Discrete Applied Mathematics 23 1 11 24 algorithms graph parameterized