登入選單

返回Google圖書搜尋

Computing Transitive Closure on Systolic Arrays of Fixed Size

Björn LisperSwedish Institute of Computer Science

出版	Swedish Institute of Computer Science, 1989
URL	http://books.google.com.hk/books?id=zzXwGwAACAAJ&hl=&source=gbs_api

註釋

Abstract: "Forming the transitive closure of a binary relation (or directed graph) is an important part of many algorithms. When the relation is represented by a bit matrix, the transitive closure can be efficiently computed in parallel in a systolic array. Various such arrays for computing the transitive closure have been proposed. They all have in common, though, that the size of the array must be proportional to the number of nodes. Here we propose two ways of computing the transitive closure of an arbitrary big graph on a systolic array of fixed size. The first method is a simple partitioning of a well-known systolic algorithm for computing the transitive closure