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

DOI10.1016/0020-0190(92)90115-CzbMath0768.68169MaRDI QIDQ1195488

Shen-Lung Peng, Maw-Shang Chang

Publication date: 29 November 1992

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

zbMATH Keywords

NP-hardlinear time algorithmdominating setsstrongly chordal graphdomatic partition problem

Mathematics Subject Classification ID

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

Related Items (7)

Transversal partitioning in balanced hypergraphs ⋮ Loose cover of graphs ⋮ Rainbow domination and related problems on strongly chordal graphs ⋮ Strongly simplicial vertices of powers of trees ⋮ 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 ⋮ The domatic number problem on some perfect graph families

Cites Work

• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• Dominating sets and domatic number of circular arc graphs
• On the domatic number of interval graphs
• Linear algorithm for domatic number problem on interval graphs
• Triangulated graphs and the elimination process
• Three Partition Refinement Algorithms
• The edge inducibility of graphs
• Dominating Sets in Chordal Graphs
• Towards a theory of domination in graphs
• The Domatic Number Problem in Interval Graphs

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