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

zbMATH Open1274.05199MaRDI QIDQ4909684FDOQ4909684

Authors: Vincent Ranwez, Stefan Janaqi, Sylvie Ranwez 

Publication date: 21 March 2013

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

zbMATH Keywords

directed acyclic graphclosure operatordagleast common ancestor

Mathematics Subject Classification ID

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

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)