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

From MaRDI portal
Revision as of 02:15, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Linear time algorithms for NP-hard problems restricted to partial k- trees
scientific article

    Statements

    Linear time algorithms for NP-hard problems restricted to partial k- trees (English)
    0 references
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    NP-hard problems on graphs
    0 references
    linear time algorithms for trees
    0 references
    optimization
    0 references
    dynamic programming
    0 references

    Identifiers