A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs |
| |
| Authors: | B.S. Panda Sajal K. Das |
| |
| Affiliation: | a Computer Science and Application Group, Department of Mathematics, Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110 016, India
b Department of Computer Science and Engineering, The University of Texas at Arlington, Arlington, TX 76019, USA |
| |
| 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. |
| |
| Keywords: | Graph algorithms Parallel algorithms Chordal graphs Proper interval graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
