Test se un dato DAG è un reticolo

Question

Mi viene dato un grafico aciclico diretto (DAG) con una fonte e un lavandino unici. Esiste un modo efficiente per verificare se il ordine parziale rappresentato da questo grafico è un reticolo?

In altre parole, devo testare se due vertici hanno a unico Il limite inferiore e il massimo limite inferiore.

Dalla breve navigazione, ho trovato un algoritmo $ O (n^3) $ che calcola esplicitamente il limite superiore di ogni coppia di elementi. C'è un test migliore?