Domination and total domination on asteroidal triple-free graphs

Domination and total domination on asteroidal triple-free graphs

0.00 Avg rating0 Votes
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:
Abstract:

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(n6) on asteroidal-triple free graphs and in time O(n7) on graphs with dominating shortest path.

Reviews

Required fields are marked *. Your email address will not be published.