On-line computation of transitive closures of graphs

DOI10.1016/0020-0190(83)90033-9zbMath0514.68062OpenAlexW2043190038MaRDI QIDQ1051432

Naoki Katoh, Toshihide Ibaraki

Publication date: 1983

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(83)90033-9

zbMATH Keywords

directed graphtransitive closureon-line computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

Modular materialisation of Datalog programs, NC algorithms for dynamically solving the all pairs shortest paths problem and related problems, Amortized efficiency of a path retrieval data structure, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, On-line 2-satisfiability, A data structure for arc insertion and regular path finding, Finding paths and deleting edges in directed acyclic graphs, Nonrecursive incremental evaluation of Datalog queries, Mantaining dynamic matrices for fully dynamic transitive closure, Symbolic state-space exploration and numerical analysis of state-sharing composed models, A special case the of dynamization problem for least cost paths, On-line computation of minimal and maximal length paths, Credibility dynamics: a belief-revision-based trust model with pairwise comparisons, A fully dynamic algorithm for maintaining the transitive closure, Dynamic cycle detection, Speeding up dynamic transitive closure for bounded degree graphs

Cites Work

• Unnamed Item
• Gaussian elimination is not optimal
• An On-Line Edge-Deletion Problem
• On the Asymptotic Complexity of Matrix Multiplication
• Efficiency of a Good But Not Linear Set Union Algorithm
• Set Merging Algorithms