The transitive closure of a given DAG , with n vertices and m edges , may be constructed in time O ( mn ) by using either breadth @-@ first search or depth @-@ first search to test reachability from each vertex . Alternatively , it can be solved in time O ( nω ) where ω < 2 @.@ 373 is the exponent for fast matrix multiplication algorithms ; this is a theoretical improvement over the O ( mn ) bound for dense graphs .