Nordic Journal of Computing Bibliography

Maria Andreou and Stavros D. Nikolopoulos. NC Coloring Algorithms for Permutation Graphs. Nordic Journal of Computing, 6(4):422-445, Winter 1999.
Abstract

We show that the problem of coloring a permutation graph of size n can be solved in O(log n log k) time using O(kn2 / log k log2n) processors on the CREW PRAM model of computation, where 1 < k < n. We estimate the parameter k on random permutation graphs and show that the coloring problem can be solved in O(log n log log n) time in the average-case on the CREW PRAM model of computation with O(n2) processors. Our computational strategy goes as follows: Given a permutation pi or its corresponding permutation graph G[pi], we first construct a directed acyclic graph G*[pi] using certain combinatorial properties of pi, and then compute longest paths in the directed acyclic graph using divide-and-conquer techniques. We show that the problem of coloring a permutation graph G[pi] is equivalent to finding longest paths in its acyclic digraph G*[pi]. The best-known parallel algorithms for the same problem run in O(log2n) time using O(n3/ log n) processors on the CREW PRAM model of computation.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: parallel algorithms, perfect graphs, permutation graphs, coloring problem, directed acyclic graphs, longest paths

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database