Assertion: directed graph | /r/HasProperty | dag
Facets:
value: in linear time
type: TEMPORAL
value: if
type: DEGREE
Source sentences:
text: The existence of such an ordering can be used to characterize DAGs: a directed graph is a DAG if and only if it has a topological ordering.
text: It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is valid or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.