Labeling algorithms for domination problems in sun-free chordal graphs (Q1117254): Difference between revisions

This paper deals with efficient algorithms for solving domination problems. After a detailed introduction the author presents a linear algorithm which solves the k-domination problem in sun-free chordal graphs without taking powers. In section 3, he uses the algorithm for the Steiner tree problem to solve the connected domination problem in sun- free chordal graphs. Finally in section 4, the author gives a linear algorithm for the total domination problem in sun-free chordal graphs. In the fifth section, he proves some NP-complete results for variations of the k-domination problem, where k is a fixed positive integer.