1997/11/01 by Jan Arne Telle, Andrzej Proskurowski · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems #Treewidth #Mathematics #Vertex (graph theory) #Algorithm #Bounded function #Time complexity #Tree decomposition #Vertex cover #Combinatorics #Discrete mathematics #Graph #Pathwidth
paper · doi:10.1137/s0895480194275825
openalex publication_date 1997/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
In this paper, we consider a large class of vertex partitioning problems and apply to them the theory of algorithm design for problems restricted to partial k-trees. We carefully describe the details of algorithms and analyze their complexity in an attempt to make the algorithms feasible as solutions for practical applications. We give a precise characterization of vertex partitioning problems, which include domination, coloring and packing problems, and their variants. Several new graph parameters are introduced as generalizations of classical parameters. This characterization provides a basis for a taxonomy of a large class of problems, facilitating their common algorithmic treatment and allowing their uniform complexity classification. We present a design methodology of practical solution algorithms for generally \NP-hard problems when restricted to partial k-trees (graphs with treewidth bounded by k). This "practicality" accounts for dependency on the parameter k of the computational complexity of the resulting algorithms. By adapting the algorithm design methodology on partial k-trees to vertex partitioning problems, we obtain the first algorithms for these problems with reasonable time complexity as a function of treewidth. As an application of the methodology, we give the first polynomial-time algorithm on partial k-trees for computation of the Grundy number.