Efficient determination of the transitive closure of a directed graph
From MaRDI portal
Publication:2547483
DOI10.1016/0020-0190(71)90006-8zbMath0221.68030OpenAlexW2140232587WikidataQ29042360 ScholiaQ29042360MaRDI QIDQ2547483
Publication date: 1971
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(71)90006-8
Related Items
An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs ⋮ Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs ⋮ The complexity of Boolean matrix root computation ⋮ Unnamed Item ⋮ An improved combinatorial algorithm for Boolean matrix multiplication ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ On Making Directed Graphs Transitive ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Skew-polynomial-sparse matrix multiplication ⋮ An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs ⋮ On making directed graphs transitive ⋮ Complexité de problèmes liés aux graphes sans circuit ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ All-pairs bottleneck paths in vertex weighted graphs ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ A simple approach to nondecreasing paths ⋮ Finding strong bridges and strong articulation points in linear time ⋮ All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ Applications of graph theory in computer systems ⋮ Revealed preference theory: an algorithmic outlook ⋮ Limitations of incremental dynamic programming ⋮ On efficiently computing the product of two binary relations ⋮ On pure structure of dynamic systems ⋮ Algebraic methods in the congested clique ⋮ On the vector representation of the reachability in planar directed graphs ⋮ Thick 2D relations for document understanding ⋮ Computational experiences with some transitive closure algorithms ⋮ Unnamed Item ⋮ Computing a graph's period quadratically by node condensation ⋮ An improved transitive closure algorithm ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Unnamed Item ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Bit complexity of matrix products
Cites Work
