The optimal sequential and parallel algorithms to compute all hinge vertices on interval graphs |
| |
| Authors: | Debashis Bera Madhumangal Pal Tapan K. Pal |
| |
| Affiliation: | 1. Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore - 721 102, West Bengal, India
|
| |
| Abstract: | If the distance between two vertices becomes longer after the removal of a vertexu, thenu is called a hinge vertex. In this paper, a linear time sequential algorithm is presented to find all hinge vertices of an interval graph. Also, a parallel algorithm is presented which takesO(n/P + logn) time usingP processors on an EREW PRAM. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
