Domination and total domination on asteroidal triple-free graphs
type: Item
instance of: scholarly article
title: Domination and total domination on asteroidal triple-free graphs
zbMATH Open document ID: 0943.05063
DOI: 10.1016/S0166-218X(99)00128-6
author: Dieter Kratsch
published in: Discrete Applied Mathematics
publication date: 2000-08-30T00:00:00Z
review text: An asteroidal triple (AT) of an undirected graph \(G\) is a set of three vertices of \(G\) such that there is a path between any two of them avoiding the neighborhood of the third one. A graph is AT-free if it contains no AT. The structure and algorithmic properties of AT-free graphs have been studied extensively---AT-free graphs generalize well-known graph classes such as interval, permutation, trapezoid and cocomparability graphs. This paper presents polynomial time algorithms for solving the problems DOMINATING SET and TOTAL DOMINATING SET restricted to AT-free graphs. These algorithms even work in polynomial time on graphs with dominating shortest path---a generalization of AT-free graphs. The key idea of the algorithms is to compute a certain type of dominating set by dynamic programming through the levels of a BFS-tree.
reviewed by: Andreas Brandstädt
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1395007
zbMATH Keywords: total domination
zbMATH Keywords: asteroidal triple
zbMATH Keywords: AT-free graphs
zbMATH Keywords: polynomial time algorithms
zbMATH Keywords: dominating set
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Connected domination and steiner set on asteroidal triple-free graphs
cites work: Independent sets in asteroidal triple-free graphs
cites work: Labeling algorithms for domination problems in sun-free chordal graphs
cites work: A linear time algorithm to compute a dominating path in an AT-free graph
cites work: Linear time algorithms for dominating pairs in asteroidal triple-free graphs
cites work: Asteroidal Triple-Free Graphs
cites work: Clustering and domination in perfect graphs
cites work: Dominating sets in perfect graphs
cites work: On Hadwiger's Number and the Stability Number
cites work: Independence and domination in polygon graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Domination in permutation graphs
cites work: Q3328583
cites work: Q4368728
cites work: Q4368729
cites work: Introduction to ``Topics on Domination''
cites work: The NP-completeness column: An ongoing guide
cites work: The complexity of domination problems in circle graphs
cites work: Domination on Cocomparability Graphs
cites work: Total domination and transformation
cites work: An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
cites work: Computing the Minimum Fill-In is NP-Complete
Wikidata QID: Q127343082
description: scientific article; zbMATH DE number 1395007