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

DOI10.1016/0020-0190(92)90115-CzbMATH Open0768.68169MaRDI QIDQ1195488FDOQ1195488

Authors: Shen-Lung Peng, Maw-Shang Chang 

Publication date: 29 November 1992

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

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

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)

Cites Work

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

Cited In (10)

• Independent domatic partitioning or fall coloring of strongly chordal graphs
• The domatic number problem on some perfect graph families
• The upper domatic number of a graph
• Domination, independent domination, and duality in strongly chordal graphs
• 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)