A linear algorithm for finding a minimum dominating set in a cactus
type: Item
instance of: scholarly article
title: A linear algorithm for finding a minimum dominating set in a cactus
zbMATH Open document ID: 0596.05051
DOI: 10.1016/0166-218X(86)90089-2
author: John Pfaff
author: Stephen T. Hedetniemi
author: Renu C. Laskar
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: A cactus is a graph in which each block is either an edge or a cycle. In this paper, a linear time algorithm for finding a minimum order dominating set in a cactus is presented.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3959480
zbMATH Keywords: cactus
zbMATH Keywords: linear time algorithm
zbMATH Keywords: minimum order dominating set
reviewed by: Maciej M. Sysło
MaRDI profile type: Publication
cites work: Q3941433
cites work: Dominating Sets in Chordal Graphs
cites work: Q4163262
cites work: A linear algorithm for the domination number of a tree
cites work: Towards a theory of domination in graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q3933018
cites work: Optimum domination in weighted trees
full work available at URL: 0166-218x(86)90089-2
OpenAlex ID: W2008228846
description: scientific article; zbMATH DE number 3959480