|
|||||
|
|
Recognizing and representing proper interval graphs in parallel using merging and sorting |
|
| Authors: | Jørgen Bang-Jensen |
| Institution: | a Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark b Department of Mathematics and Statistics, University of Victoria, Victoria, BC, Canada V8W 3P4 c School of CTI, DePaul University, 243 South Wabash Avenue, Chicago, IL 60604, USA |
| Abstract: | We present a parallel algorithm for recognizing and representing a proper interval graph in  time with 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]. |
| Keywords: | Proper interval graph Parallel sorting |
| 本文献已被 ScienceDirect 等数据库收录！ | |