A uniform approach to semi-dynamic problems on digraphs

DOI10.1016/S0304-3975(97)00288-0zbMath0917.68087OpenAlexW2031868890MaRDI QIDQ1274321

Serafino Cicerone, Francesco Pugliese, Umberto Nanni, Daniele Frigioni

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00288-0

zbMATH Keywords

transitive closuredirected acyclic graphsdynamic graph algorithmsdominator tree

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (3)

Average-Case Analysis of Online Topological Ordering ⋮ Average-case analysis of incremental topological ordering ⋮ Dynamic Dominators and Low-High Orders in DAGs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Amortized efficiency of a path retrieval data structure
• Computing dominators in parallel
• Algorithms of placing recovery points
• Finding paths and deleting edges in directed acyclic graphs
• Fast Algorithms for Finding Nearest Common Ancestors
• A fast algorithm for finding dominators in a flowgraph
• Incremental algorithms for minimal length paths
• Optimal algorithm for the nearest common dominator problem
• Finding Dominators in Directed Graphs
• Faster shortest-path algorithms for planar graphs

This page was built for publication: A uniform approach to semi-dynamic problems on digraphs