A Dynamic Programming Approach to the Dominating Set Problem on k-Trees

DOI10.1137/0608044zbMath0635.05040OpenAlexW1975479672MaRDI QIDQ3773922

J. Mark Keil, Derek Gordon Corneil

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0608044

zbMATH Keywords

dynamic programmingdominating setchordal graphsk-trees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Related Items (21)

A recurrence template for several parameters in series-parallel graphs ⋮ Linear time algorithms for NP-hard problems restricted to partial k- trees ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ The weighted perfect domination problem ⋮ Dominating sets in perfect graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ An optimal algorithm for finding dominating cycles in circular-arc graphs ⋮ On the SPANNING \(k\)-TREE problem ⋮ Locating facilities which interact: Some solvable cases ⋮ Total domination in interval graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ The complexity of domination problems in circle graphs ⋮ SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Using a hybrid of exact and genetic algorithms to design survivable networks ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ The complexity of generalized clique covering ⋮ Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• Unnamed Item
• A linear algorithm for the domination number of a tree
• A linear algorithm for the domination number of a series-parallel graph
• The concept of state in discrete dynamic programming
• Decomposing a Polygon into Simpler Components
• Dominating Sets in Chordal Graphs
• Isomorphism Testing in Hookup Classes
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: A Dynamic Programming Approach to the Dominating Set Problem on k-Trees