A simple linear time algorithm for the domatic partition problem on strongly chordal graphs

DOI10.1016/0020-0190(92)90115-CMaRDI QIDQ1195488zbMATH OpenFDO

Authors Shen-Lung Peng, Maw-Shang Chang

Publication date 29 November 1992

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

dominating setsNP-hardlinear time algorithmstrongly chordal graphdomatic partition problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A linear time algorithm for graph partition problems
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• scientific article; zbMATH DE number 2086689
• scientific article; zbMATH DE number 4045183
• A linear-time algorithm for semitotal domination in strongly chordal graphs
• A note on the complexity of the total domatic partition problem in graphs
• The algorithmic complexity of \(k\)-domatic partition of graphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• A strong formulation for the graph partition problem
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Characterizations of strongly chordal graphs
• Dominating Sets in Chordal Graphs
• Dominating sets and domatic number of circular arc graphs
• Domination, independent domination, and duality in strongly chordal graphs
• Linear algorithm for domatic number problem on interval graphs
• On the domatic number of interval graphs
• The Domatic Number Problem in Interval Graphs
• The edge inducibility of graphs
• Three Partition Refinement Algorithms
• Towards a theory of domination in graphs
• Triangulated graphs and the elimination process

Cited in

(10)

• Independent domatic partitioning or fall coloring of strongly chordal graphs
• The domatic number problem on some perfect graph families
• Domination, independent domination, and duality in strongly chordal graphs
• The upper domatic number of a graph
• On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
• Strongly simplicial vertices of powers of trees
• Loose cover of graphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• Rainbow domination and related problems on strongly chordal graphs
• Transversal partitioning in balanced hypergraphs

This page was built for publication: A simple linear time algorithm for the domatic partition problem on strongly chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1195488)