An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model

DOI10.1016/0020-0190(92)90249-UzbMath0764.68055MaRDI QIDQ1195857

Ming-Shing Yu, Cheng-Hsing Yang

Publication date: 4 January 1993

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

zbMATH Keywords

data structuresdesign of algorithmsparallel algorithminterval graphsdomatic partition problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (1)

Transversal partitioning in balanced hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Sorting in \(c \log n\) parallel steps
• Dominating sets and domatic number of circular arc graphs
• On the domatic number of interval graphs
• A linear algorithm for the domination number of a tree
• Linear algorithm for domatic number problem on interval graphs
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Parallel Merge Sort
• An Optimal Solution for the Channel-Assignment Problem
• Parallel Prefix Computation
• Parallel Scheduling Algorithms
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• Towards a theory of domination in graphs
• The Domatic Number Problem in Interval Graphs

This page was built for publication: An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model