An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
From MaRDI portal
Publication:1075771
DOI10.1016/0020-0190(86)90021-9zbMath0592.68063OpenAlexW2038086027MaRDI QIDQ1075771
Michel Minoux, Brigitte Jaumard
Publication date: 1986
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(86)90021-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Determining connected components in linear time by a linear number of processors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A sensitive transitive closure algorithm
- An algorithm for finding the transitive closure of a digraph
- A cascade algorithm for the logical closure of a set of binary relations
- Computational experiences with some transitive closure algorithms
- On computing the transitive closure of a relation
- Algebraic structures for transitive closure
- Improved time and space bounds for Boolean matrix multiplication
- An improved transitive closure algorithm
- Gaussian elimination is not optimal
- Efficient determination of the transitive closure of a directed graph
- Linear expected-time algorithms for connectivity problems
- On the Asymptotic Complexity of Matrix Multiplication
- A modification of Warshall's algorithm for the transitive closure of binary relations
- A transitive closure algorithm
- Depth-First Search and Linear Graph Algorithms
- A fast expected time algorithm for Boolean matrix multiplication and transitive closure
- A Theorem on Boolean Matrices
