Optimal algorithm for the nearest common dominator problem

DOI10.1016/0196-6774(92)90063-IMaRDI QIDQ4015269zbMATH OpenFDO

Authors Jeff I. Chu

Publication date 12 January 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(92)90063-I

zbMATH Keywords

directed acyclic graphnearest common dominatoroptimal algorithmshortest path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Lowest common ancestors in trees and directed acyclic graphs
• Finding dominators revisited (extended abstract)
• Solving shortest paths efficiently on nearly acyclic directed graphs
• Finding least common ancestors in directed acyclic graphs
• Computing Frequency Dominators and Related Problems

Cited in

(2)

• A uniform approach to semi-dynamic problems on digraphs
• Counting edges in a dag

This page was built for publication: Optimal algorithm for the nearest common dominator problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4015269)