A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
type: Item
instance of: scholarly article
title: A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
zbMATH Open document ID: 0768.68169
DOI: 10.1016/0020-0190(92)90115-C
author: Shen-Lung Peng
author: Maw-Shang Chang
published in: Information Processing Letters
publication date: 1992-11-29T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 69905
zbMATH Keywords: linear time algorithm
zbMATH Keywords: domatic partition problem
zbMATH Keywords: NP-hard
zbMATH Keywords: strongly chordal graph
zbMATH Keywords: dominating sets
MaRDI profile type: Publication
cites work: On the domatic number of interval graphs
cites work: Dominating sets and domatic number of circular arc graphs
cites work: Dominating Sets in Chordal Graphs
cites work: Towards a theory of domination in graphs
cites work: Characterizations of strongly chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: The edge inducibility of graphs
cites work: The Domatic Number Problem in Interval Graphs
cites work: Three Partition Refinement Algorithms
cites work: Triangulated graphs and the elimination process
cites work: Linear algorithm for domatic number problem on interval graphs
Recommended article: A linear time algorithm for graph partition problems
Recommended article: A linear-time algorithm for paired-domination problem in strongly chordal graphs
Recommended article: Q4737226
Recommended article: Q3782805
Recommended article: A linear-time algorithm for semitotal domination in strongly chordal graphs
Recommended article: Q5243986
Recommended article: The Algorithmic Complexity of k-Domatic Partition of Graphs
Recommended article: The parallel solution of domination problems on chordal and strongly chordal graphs
Recommended article: A strong formulation for the graph partition problem
Recommended article: Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
description: scientific article; zbMATH DE number 69905