An optimal pram algorithm for a spanning tree on trapezoid graphs |
| |
Authors: | Debashis Bera Madhumangal Pal Tapan K Pal |
| |
Institution: | 1. Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, 721 102, Midnapore, India
|
| |
Abstract: | LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|