A fast algorithm for computing transitive relation

Authors
Liao, PS Chen, TS Chung, PC
Citation
Ps. Liao et al., A fast algorithm for computing transitive relation, INT J COM M, 70(3), 1999, pp. 495-504
Citations number
5
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
ISSN journal
00207160 → ACNP
Volume
70
Issue
3
Year of publication
1999
Pages
495 - 504
Database
ISI
SICI code
Abstract
The transitive relation of a finite set S with size \S\ = n is verified qui ckly by the relational inequality M-2 less than or equal to M that needs 2n (3) computations. In this paper, a table oriented audit method based on mes sage passing protocol only needs 2 Sigma(node=1)(n) i(node) o(node) computa tions to conduct the verification of transitive relation and it is always l ess than the relational inequality.