An O(n m) algorithm for calculating the closure of lca-type operators.

MaRDI QIDQ4909684zbMATHFDO

Authors Vincent Ranwez, Stefan Janaqi, Sylvie Ranwez

Publication date 21 March 2013

zbMATH Keywords

directed acyclic graphclosure operatordagleast common ancestor

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Automata, Languages and Programming
• Finding least common ancestors in directed acyclic graphs
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
• Lowest common ancestors in trees and directed acyclic graphs
• New common ancestor problems in trees and directed acyclic graphs

Cited in

(1)

• GLB-closures in directed acyclic graphs and their applications

This page was built for publication: An \(O(n\cdot m)\) algorithm for calculating the closure of \(lca\)-type operators.

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