Editing Directed acyclic graph
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 25: | Line 25: | ||
:* '''[[All-pairs shortest paths]]''' can be computed in <math>O(V(E+V))</math> by <math>V</math> invocations of the single-source algorithm. This is, however, no faster than [[breadth-first search]] when the DAG is unweighted, and no faster than the [[Floyd–Warshall algorithm]] when the graph is dense (so that it is an improvement only over sparse weighted DAGs). | :* '''[[All-pairs shortest paths]]''' can be computed in <math>O(V(E+V))</math> by <math>V</math> invocations of the single-source algorithm. This is, however, no faster than [[breadth-first search]] when the DAG is unweighted, and no faster than the [[Floyd–Warshall algorithm]] when the graph is dense (so that it is an improvement only over sparse weighted DAGs). | ||
::* The same applies to the '''transitive closure problem''' – it is not easy to improve over the <math>O(V^3)</math> bound given by Warshall's algorithm, but see [[Directed acyclic graph/Transitive closure|this]] for a method that may perform better under certain circumstances. The bounds on the '''transitive reduction problem''' match those on transitive closure. | ::* The same applies to the '''transitive closure problem''' – it is not easy to improve over the <math>O(V^3)</math> bound given by Warshall's algorithm, but see [[Directed acyclic graph/Transitive closure|this]] for a method that may perform better under certain circumstances. The bounds on the '''transitive reduction problem''' match those on transitive closure. | ||
− | |||
* Identifying all strongly connected components in a digraph and contracting each component to a single vertex produces a DAG, known as the '''kernel DAG'''. Adapting the special transitive closure algorithm on DAGs to the kernel DAG gives an algorithm which may be fast for some classes of digraphs. The kernel DAG is also useful as an intermediate structure in the solutions of various other problems. | * Identifying all strongly connected components in a digraph and contracting each component to a single vertex produces a DAG, known as the '''kernel DAG'''. Adapting the special transitive closure algorithm on DAGs to the kernel DAG gives an algorithm which may be fast for some classes of digraphs. The kernel DAG is also useful as an intermediate structure in the solutions of various other problems. | ||
* The '''[[minimum spanning arborescence]] problem''' does not have much to do with DAGs in general, but an arborescence is a specific kind of DAG that looks like a tree. | * The '''[[minimum spanning arborescence]] problem''' does not have much to do with DAGs in general, but an arborescence is a specific kind of DAG that looks like a tree. |