A parallel algorithm for solving the coloring problem on trapezoid graphs

A coloring of a graph G is an assignment of colors to the vertices of G so that adjacent vertices are assigned distinct colors. The coloring problem is to color an input graph with the minimum number of colors. This problem is a well-known NP-complete problem, However, it can be solved in polynomial...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1997-06, Vol.62 (6), p.323-327
Main Authors: Nakayama, Shin-ichi, Masuyama, Shigeru
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Color
Coloring problem
Computer science
control theory
systems
Exact sciences and technology
Graphs
Information processing
Information retrieval. Graph
Parallel algorithms
Problem solving
Studies
Theoretical computing
Trapezoid graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A coloring of a graph G is an assignment of colors to the vertices of G so that adjacent vertices are assigned distinct colors. The coloring problem is to color an input graph with the minimum number of colors. This problem is a well-known NP-complete problem, However, it can be solved in polynomial time for certain classes of graphs, e.g., interval graphs, permutation graphs and trapezoid graphs. Coloring algorithms for these graphs have applications to wire routing problems for integrated circuits. In this paper, we propose a parallel algorithm for solving the coloring problem on trapezoid graphs G which runs in O( log 2 n) time using O( n 3 log n ) processors on the CREW PRAM where n is the number of vertices of G.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(97)00082-3