Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421431 | Discrete Applied Mathematics | 2007 | 15 Pages |
Abstract
We present a parallel algorithm for recognizing and representing a proper interval graph in O(log2n) time with O(m+n)O(m+n) processors on the CREW PRAM, where m and n are the number of edges and vertices in the graph. The algorithm uses sorting to compute a weak linear ordering of the vertices, from which an interval representation is easily obtained. It is simple, uses no complex data structures, and extends ideas from an optimal sequential algorithm for recognizing and representing a proper interval graph [X. Deng, P. Hell, J. Huang, Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput. 25 (2) (1996) 390–403].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jørgen Bang-Jensen, Jing Huang, Louis Ibarra,