Speeding up dynamic transitive closure for bounded degree graphs

DOI10.1007/BF01209711zbMath0790.68095OpenAlexW2067949249MaRDI QIDQ1323330

Daniel M. Yellin

Publication date: 30 June 1994

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01209711

zbMATH Keywords

digraphtransitive closurepath finding algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

NC algorithms for dynamically solving the all pairs shortest paths problem and related problems ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ On-line graph algorithms for incremental compilation ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ Maintaining a topological order under edge insertions

Cites Work

• On-line computation of transitive closures of graphs
• Amortized efficiency of a path retrieval data structure
• Finding paths and deleting edges in directed acyclic graphs
• Making data structures persistent
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Speeding up dynamic transitive closure for bounded degree graphs