On computing the transitive closure of a relation

DOI10.1007/BF00271339zbMATH Open0349.68021OpenAlexW1965253335MaRDI QIDQ1235010FDOQ1235010

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

• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• A Theorem on Boolean Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Top-down syntax nalysis
• A transitive closure algorithm
• Computational experiences with some transitive closure algorithms

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)