Fast algorithm for computing transitive relation

Ping Sung Liao, Tse Sheng Chen, Pau-Choo Chung

Research output: Contribution to journalArticlepeer-review


The transitive relation of a finite set S with size |S| = n is verified quickly by the relational inequality M2≤M that needs 2n3 computations. In this paper, a table oriented audit method based on message passing protocol only needs 2 ∑node n = node = inode·Onode computations to conduct the verification of transitive relation and it is always less than the relational inequality.

Original languageEnglish
Pages (from-to)495-504
Number of pages10
JournalInternational Journal of Computer Mathematics
Issue number3
Publication statusPublished - 1999 Jan 1

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Fast algorithm for computing transitive relation'. Together they form a unique fingerprint.

Cite this