On computing the transitive closure of a relation

DOI10.1007/BF00271339zbMath0349.68021OpenAlexW1965253335MaRDI QIDQ1235010

J. Eve, Reino Kurki-Suonio

Publication date: 1977

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

Full work available at URL: https://doi.org/10.1007/bf00271339

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20) Other classical set theory (including functions, relations, and set algebra) (03E20) Algorithms in computer science (68W99) Software, source code, etc. for problems pertaining to mathematical logic and foundations (03-04) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (6)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On computing the transitive closure of a relation