Fast algorithm for computing transitive relation

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

doi:10.1080/00207169908804770

Fast algorithm for computing transitive relation

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

Institute of Computer and Communication Engineering

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English
Pages (from-to)	495-504
Number of pages	10
Journal	International Journal of Computer Mathematics
Volume	70
Issue number	3
DOIs	https://doi.org/10.1080/00207169908804770
Publication status	Published - 1999 Jan 1

All Science Journal Classification (ASJC) codes

Computer Science Applications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1080/00207169908804770

Cite this

@article{fd9ce3d680ed48afaccf8d19238369ae,

title = "Fast algorithm for computing transitive relation",

abstract = "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.",

author = "Liao, {Ping Sung} and Chen, {Tse Sheng} and Pau-Choo Chung",

year = "1999",

month = jan,

day = "1",

doi = "10.1080/00207169908804770",

language = "English",

volume = "70",

pages = "495--504",

journal = "International Journal of Computer Mathematics",

issn = "0020-7160",

publisher = "Taylor and Francis Ltd.",

number = "3",

}

TY - JOUR

T1 - Fast algorithm for computing transitive relation

AU - Liao, Ping Sung

AU - Chen, Tse Sheng

AU - Chung, Pau-Choo

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032628072&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032628072&partnerID=8YFLogxK

U2 - 10.1080/00207169908804770

DO - 10.1080/00207169908804770

M3 - Article

AN - SCOPUS:0032628072

SN - 0020-7160

VL - 70

SP - 495

EP - 504

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 3

ER -

Fast algorithm for computing transitive relation

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this