I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice?

In other words, I need to test whether any two vertices have a unique least upper bound and greatest lower bound.

From brief browsing, I found an $O(n^3)$ algorithm that explicitly computes the least upper bound of every pair of elements. Is there a better test?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top