A simple optimal parallel algorithm for the minimum coloring problem on interval graphs

DOI10.1016/0020-0190(93)90267-DzbMath0787.68043MaRDI QIDQ1313723

Cheng-Hsing Yang, Ming-Shing Yu

Publication date: 24 February 1994

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

zbMATH Keywords

parallel algorithminterval graphsminimum coloring problem

Mathematics Subject Classification ID

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

Related Items (1)

A parallel algorithm for solving the coloring problem on trapezoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• 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
• The Complexity of Coloring Circular Arcs and Chords

This page was built for publication: A simple optimal parallel algorithm for the minimum coloring problem on interval graphs