Linear time algorithms for NP-hard problems restricted to partial k- trees (Q1116705): Difference between revisions

We present and illustrate by a sequence of examples an algorithm paradigm for solving NP-hard problems on graphs resticted 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.