Article ID: | iaor20012901 |
Country: | Netherlands |
Volume: | 99 |
Issue: | 1/3 |
Start Page Number: | 111 |
End Page Number: | 123 |
Publication Date: | Feb 2000 |
Journal: | Discrete Applied Mathematics |
Authors: | Kratsch Dieter |
We present the first polynomial time algorithms for solving the NP-complete graph problems DOMINATING SET and TOTAL DOMINATING SET when restricted to asteroidal triple-free graphs. We also present algorithms to compute a minimum cardinality dominating set and a minimum cardinality total dominating set on a large superclass of the asteroidal triple-free graphs, namely the class of those graphs for which each connected component has a so-called dominating shortest path. Our algorithms can be implemented to run in time O(