Labeling algorithms for domination problems in sun-free chordal graphs (Q1117254)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Labeling algorithms for domination problems in sun-free chordal graphs |
scientific article |
Statements
Labeling algorithms for domination problems in sun-free chordal graphs (English)
0 references
1988
0 references
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.
0 references
algorithms
0 references
sun-free chordal graphs
0 references
Steiner tree problem
0 references
total domination problem
0 references
NP-complete
0 references
k-domination
0 references
