| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427988 | Information Processing Letters | 2009 | 6 Pages |
Abstract
In this paper, we first show how a certain ordering of vertices, called bicompatible elimination ordering (BCO), of a proper interval graph can be used to solve efficiently several problems in proper interval graphs. We, then, propose an NC parallel algorithm (i.e., polylogarithmic-time employing a polynomial number of processors) in SIMD CRCW PRAM (Single Instruction Stream Multiple Data Stream Concurrent Read Concurrent Write Parallel Random Access Machine) model of parallel computation to compute a BCO of a proper interval graph. To the best of our knowledge, this is the first NC parallel algorithm to compute a BCO of a proper interval graph.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
