Editing Directed acyclic graph (section)

=== Transitive closure and transitive reduction ===
The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω''&nbsp;<&nbsp;2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>

In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>