An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs

DOI10.1016/0020-0190(86)90021-9zbMath0592.68063MaRDI QIDQ1075771

Brigitte Jaumard, Michel Minoux

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

zbMATH Keywords

directed graph; data structures; graph algorithms; list processing; circuit-free graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Determining connected components in linear time by a linear number of processors, A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities

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