On computing the transitive closure of a relation

DOI10.1007/BF00271339zbMath0349.68021MaRDI QIDQ1235010

Reino Kurki-Suonio, J. Eve

Publication date: 1977

Published in: Acta Informatica (Search for Journal in Brave)

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C20: Directed graphs (digraphs), tournaments

03E20: Other classical set theory (including functions, relations, and set algebra)

68W99: Algorithms in computer science

03-04: Software, source code, etc. for problems pertaining to mathematical logic and foundations

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs, On finding the strongly connected components in a directed graph, An efficient transitive closure algorithm for cyclic digraphs, Using basis dependence distance vectors in the modified Floyd-Warshall algorithm, Using Basis Dependence Distance Vectors to Calculate the Transitive Closure of Dependence Relations by Means of the Floyd-Warshall Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational experiences with some transitive closure algorithms
• Top-down syntax nalysis
• A transitive closure algorithm
• Depth-First Search and Linear Graph Algorithms
• A Theorem on Boolean Matrices