Nordic Journal of Computing Bibliography

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(kn² / log k log²n) 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(n²) 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(log²n) time using O(n³/ 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

• Andreas Brandstädt and Dieter Kratsch. On domination problems for permutation and other graphs. Theoretical Computer Science, 54(2-3):181-198, October 1987.

• A. Datta, A. Maheshwari, and J.-R. Sack. Optimal Parallel Algorithms for Direct Dominance Problems. Nordic Journal of Computing, 3(1):72-88, Spring 1996.

• Martin Farber and J. Mark Keil. Domination in permutation graphs. Journal of Algorithms, 6(3):309-321, September 1985.

• Jeremy Spinrad. On comparability and permutation graphs. SIAM Journal on Computing, 14(3):658-670, August 1985.

• Ming-Shing Yu, Lin Yu Tseng, and Shoe-Jane Chang. Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs. Information Processing Letters, 46(1):7-11, 29 April 1993.

Shortcuts: