Amortized efficiency of a path retrieval data structure

DOI10.1016/0304-3975(86)90098-8zbMath0638.68065OpenAlexW1976177462WikidataQ61609681 ScholiaQ61609681MaRDI QIDQ1099629

Giuseppe F. Italiano

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90098-8

zbMATH Keywords

path retrieval data structure

Mathematics Subject Classification ID

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

Related Items (23)

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 ⋮ A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ Nonrecursive incremental evaluation of Datalog queries ⋮ Implied Set Closure and Its Application to Memory Consistency Verification ⋮ On-line graph algorithms for incremental compilation ⋮ Average case analysis of fully dynamic connectivity for directed graphs ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ Dynamic maintenance of directed hypergraphs ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ Recursive max-linear models with propagating noise ⋮ On-line computation of minimal and maximal length paths ⋮ Maintenance of 2- and 3-edge-connected components of graphs. I ⋮ Dynamic reachability in planar digraphs with one source and one sink ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ Maintenance of triconnected components of graphs ⋮ A uniform approach to semi-dynamic problems on digraphs ⋮ Temporal stratification tests for linear and branching-time deductive databases ⋮ Average case analysis of fully dynamic reachability for directed graphs ⋮ Maintaining a topological order under edge insertions ⋮ Speeding up dynamic transitive closure for bounded degree graphs

Cites Work

• Unnamed Item
• On-line computation of transitive closures of graphs
• Parallel concepts in graph theory
• Dynamically switching vertices in planar graphs
• On the computational power of pushdown automata
• Amortized Computational Complexity
• Minimal Representation of Directed Hypergraphs
• Worst-case Analysis of Set Union Algorithms
• An On-Line Edge-Deletion Problem

This page was built for publication: Amortized efficiency of a path retrieval data structure