Total domination and transformation

✍ Scribed by Dieter Kratsch; Lorna Stewart

• Book ID: 104137450
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 364 KB
• Volume: 63
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00115-4

✦ Synopsis

Using a linear time many-one reduction from the problem TOTAL DOMINATING SET to the problem DOMINATING SET we show how to obtain efficient algorithms to compute a minimum cardinality total dominating set on a variety of graph classes, among them permutation graphs, dually chordal graphs and k-polygon graphs. @