On computing the transitive closure of a relation

DOI10.1007/BF00271339MaRDI QIDQ1235010zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• scientific article; zbMATH DE number 3340124 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A transitive closure algorithm
• Computational experiences with some transitive closure algorithms
• Depth-First Search and Linear Graph Algorithms
• Top-down syntax nalysis

Cited in

(7)

• Finding strong components using depth-first search
• Using basis dependence distance vectors to calculate the transitive closure of dependence relations by means of the Floyd-Warshall algorithm
• Stubborn Sets, Frozen Actions, and Fair Testing
• On finding the strongly connected components in a directed graph
• Using basis dependence distance vectors in the modified Floyd-Warshall algorithm
• An efficient transitive closure algorithm for cyclic digraphs
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1235010)