Total domination in block graphs
type: Item
instance of: scholarly article
title: Total domination in block graphs
zbMATH Open document ID: 0678.90086
DOI: 10.1016/0167-6377(89)90034-5
published in: Operations Research Letters
publication date: 1989-01-01T00:00:00Z
review text: A set of vertices D is a total dominating set for a graph G if every vertex of G is adjacent with at least one vertex in D. Although the problem of determining the minimum cardinality of a total dominating set for an arbitrary graph is NP-complete, polynomial time algorithm are known for certain classes of graphs (e.g. trees, interval graphs). The paper contains an \(O(| V| +| E|)\) time algorithm which solves this problem for block graphs. In fact, the algorithm presented here deals with a more general problem which, for particular instances, gives solutions for both domination and total domination problems.
reviewed by: C.Radu
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4112410
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: block graphs
zbMATH Keywords: total domination
author: Gerard Jennhwa Chang
MaRDI profile type: Publication
full work available at URL: 0167-6377(89)90034-5
OpenAlex ID: W2060286450
cites work: On the computational power of pushdown automata
cites work: Dominating Sets in Chordal Graphs
cites work: R-domination of block graphs
cites work: The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
cites work: Covering, Packing and Generalized Perfection
cites work: A linear algorithm for the domination number of a tree
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Domination in permutation graphs
cites work: Q4198056
cites work: The NP-completeness column: An ongoing guide
cites work: Total domination in interval graphs
cites work: A linear algorithm for the domination number of a series-parallel graph
cites work: Q3791195
cites work: On the Algorithmic Complexity of Total Domination
cites work: Q3688433
cites work: R -Domination in Graphs
description: scientific article; zbMATH DE number 4112410