889:. Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way. Alternatively, a topological ordering may be constructed by reversing a
509:
cycle would have to be oriented the wrong way. Therefore, every graph with a topological ordering is acyclic. Conversely, every directed acyclic graph has at least one topological ordering. The existence of a topological ordering can therefore be used as an equivalent definition of a directed acyclic graphs: they are exactly the graphs that have topological orderings. In general, this ordering is not unique; a DAG has a unique topological ordering if and only if it has a directed path containing all the vertices, in which case the ordering is the same as the order in which the vertices appear in the path.
357:
438:
783:
1242:. In general, the output of these blocks cannot be used as the input unless it is captured by a register or state element which maintains its acyclic properties. Electronic circuit schematics either on paper or in a database are a form of directed acyclic graphs using instances or components to form a directed reference to a lower level component. Electronic circuits themselves are not necessarily acyclic or directed.
458:
1194:
952:
416:. Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation. Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler
1425:, the triangulation changes by replacing one triangle by three smaller triangles when each point is added, and by "flip" operations that replace pairs of triangles by a different pair of triangles. The history DAG for this algorithm has a vertex for each triangle constructed as part of the algorithm, and edges from each triangle to the two or three other triangles that replace it. This structure allows
167:
1353:
1182:
value from another cell. In such a case, the value that is used must be recalculated earlier than the expression that uses it. Topologically ordering the dependency graph, and using this topological order to schedule the cell updates, allows the whole spreadsheet to be updated with only a single evaluation per cell. Similar problems of task ordering arise in
799:
136:. As a special case, every vertex is considered to be reachable from itself (by a path with zero edges). If a vertex can reach itself via a nontrivial path (a path with one or more edges), then that path is a cycle, so another way to define directed acyclic graphs is that they are the graphs in which no vertex can reach itself via a nontrivial path.
155:
22:
1563:
of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than
1209:
of a project rather than specific tasks to be performed. Instead, a task or activity is represented by an edge of a DAG, connecting two milestones that mark the beginning and completion of the task. Each such edge is labeled with an estimate for the amount of time that it will take a team of workers
1181:
changes, it is necessary to recalculate the values of other cells that depend directly or indirectly on the changed cell. For this problem, the tasks to be scheduled are the recalculations of the values of individual cells of the spreadsheet. Dependencies arise when an expression in one cell uses a
1074:
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
508:
of a directed graph is an ordering of its vertices into a sequence, such that for every edge the start vertex of the edge occurs earlier in the sequence than the ending vertex of the edge. A graph that has a topological ordering cannot have any cycles, because the edge into the earliest vertex of a
112:
in a directed graph is a sequence of edges having the property that the ending vertex of each edge in the sequence is the same as the starting vertex of the next edge in the sequence; a path forms a cycle if the starting vertex of its first edge equals the ending vertex of its last edge. A directed
1453:
the vertices are documents with a single publication date. The edges represent the citations from the bibliography of one document to other necessarily earlier documents. The classic example comes from the citations between academic papers as pointed out in the 1965 article "Networks of
Scientific
1375:
may be seen as directed acyclic graphs, with a vertex for each family member and an edge for each parent-child relationship. Despite the name, these graphs are not necessarily trees because of the possibility of marriages between relatives (so a child has a common ancestor on both the mother's and
1291:
Graphs in which vertices represent events occurring at a definite time, and where the edges always point from the early time vertex to a late time vertex of the edge, are necessarily directed and acyclic. The lack of a cycle follows because the time associated with a vertex always increases as you
900:
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
1591:
to the variables is the value at the sink found by following a path, starting from the single source vertex, that at each non-sink vertex follows the outgoing edge labeled with the value of that vertex's variable. Just as directed acyclic word graphs can be viewed as a compressed form of tries,
1576:, such as English words. Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a
1252:, and the connections between the outputs of some operations and the inputs of others. These languages can be convenient for describing repetitive data processing tasks, in which the same acyclically-connected collection of operations is applied to many data items. They can be executed as a
73:, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling).
1308:. In the version history example below, each version of the software is associated with a unique time, typically the time the version was saved, committed or released. In the citation graph examples below, the documents are published at one time and can only refer to older documents.
1339:
The converse is also true. That is in any application represented by a directed acyclic graph there is a causal structure, either an explicit order or time in the example or an order which can be derived from graph structure. This follows because all directed acyclic graphs have a
1101:. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the
1518:
gives a directed acyclic graph, it is a useful model when looking for analytic calculations of properties unique to directed acyclic graphs. For instance, the length of the longest path, from the n-th node added to the network to the first node in the network, scales as
1478:, earlier patents which are relevant to the current patent claim. By taking the special properties of directed acyclic graphs into account, one can analyse citation networks with techniques not available when analysing the general graphs considered in many studies using
1263:, straight line code (that is, sequences of statements without loops or conditional branches) may be represented by a DAG describing the inputs and outputs of each of the arithmetic operations performed within the code. This representation allows the compiler to perform
1587:, a DAG-based data structure for representing binary functions. In a binary decision diagram, each non-sink vertex is labeled by the name of a binary variable, and each sink and each edge is labeled by a 0 or 1. The function value for any
1399:, generally has the structure of a directed acyclic graph, in which there is a vertex for each revision and an edge connecting pairs of revisions that were directly derived from each other. These are not trees in general due to merges.
707:
1226:
A directed acyclic graph may be used to represent a network of processing elements. In this representation, data enters a processing element through its incoming edges and leaves the element through its outgoing edges.
1125:, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as
1319:
represents a system of probabilistic events as vertices in a directed acyclic graph, in which the likelihood of an event may be calculated from the likelihoods of its predecessors in the DAG. In this context, the
1486:
gives new insights into the citation distributions found in different applications highlighting clear differences in the mechanisms creating citations networks in different contexts. Another technique is
1296:
in the graph so you can never return to a vertex on a path. This reflects our natural intuition that causality means events can only affect the future, they never affect the past, and thus we have no
1474:
provide another example as judges support their conclusions in one case by recalling other earlier decisions made in previous cases. A final example is provided by patents which must refer to earlier
1580:. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex.
424:
of a partial order is a drawing of the transitive reduction in which the orientation of every edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
1572:
in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of
1170:
is a graph that has a vertex for each object to be updated, and an edge connecting two objects whenever one of them needs to be updated earlier than the other. A cycle in this graph is called a
3085:
1218:
of the project, the one that controls the total time for the project. Individual milestones can be scheduled according to the lengths of the longest paths ending at their vertices.
1174:, and is generally not allowed, because there would be no way to consistently schedule the tasks involved in the cycle. Dependency graphs without circular dependencies form DAGs.
69:), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be
1506:
but it is simple enough to allow for analytic solutions for some of its properties. Many of these can be found by using results derived from the undirected version of the
1154:
for systems of tasks with ordering constraints. An important class of problems of this type concern collections of objects that need to be updated, such as the cells of a
1053:
1332:, the vertices of which represent either decisions to be made or unknown information, and the edges of which represent causal influences from one vertex to another. In
829:) is a DAG in which there is at most one directed path between any two vertices. Equivalently, it is a DAG in which the subgraph reachable from any vertex induces an
1549:
1113:
Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find
1075:
the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.
451:
goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.
1565:
1311:
Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent
1205:(PERT), a method for management of large human projects that was one of the first applications of DAGs. In this method, the vertices of a DAG represent
554:
570:
1202:
329:
into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set
3387:
3254:
3015:
2981:
2946:
2909:
2791:
2764:
2737:
2700:
2673:
2612:
2585:
2552:
2525:
2498:
2471:
2429:
2173:
1923:
1876:
1849:
1835:
1819:
1792:
1765:
1730:
1654:
1624:
516:
of the reachability relation for the DAG, so any two graphs representing the same partial order have the same set of topological orders.
232:). However, different DAGs may give rise to the same reachability relation and the same partial order. For example, a DAG with two edges
1388:
descent (father-son relationships) are trees within this graph. Because no one can become their own ancestor, family trees are acyclic.
1417:
representing the version history of a geometric structure over the course of a sequence of changes to the structure. For instance in a
2048:
3292:
2639:
2248:
2160:
based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g.
2126:
1700:
1197:
PERT chart for a project with five milestones (labeled 10–50) and six tasks (labeled A–F). There are two critical paths, ADF and BC.
1344:, i.e. there is at least one way to put the vertices in an order such that all edges point in the same direction along that order.
1093:
takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices
3453:
1324:
of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called
1264:
104:
connecting pairs of vertices, where the vertices can be any kind of object that is connected in pairs by edges. In the case of a
1433:
in the
Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains
2412:
Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C. (2014), "On the shape of circular dependencies in Java programs",
1268:
1206:
1271:
states that the dependencies between modules or components of a large software system should form a directed acyclic graph.
1964:
1328:), and then replacing all directed edges by undirected edges. Another type of graph with a similar causal structure is an
995:
into a single supervertex. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are
1511:
2381:
Cormen et al. 2001, Sections 24.1, The
Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.
2338:
2235:
1989:
1392:
992:
964:
93:
3120:
Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S. (2015), "Transitive reduction of citation networks",
2457:
1466:
of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in
984:
956:
913:
for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting
851:
1256:
in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.
1130:
1336:, for instance, these diagrams are often used to estimate the expected value of different choices for intervention.
2116:
1274:
914:
856:
2240:
1573:
2079:
in Proc. 3rd Annual
Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
3448:
1238:
that computes a function of an input, where the input and output of the function are represented as individual
372:
of a DAG is the graph with the fewest edges that has the same reachability relation as the DAG. It has an edge
3370:
Friedman, S. J.; Supowit, K. J. (1987), "Finding the optimal variable ordering for binary decision diagrams",
3083:
Price, Derek J. de Solla (1976), "A general theory of bibliometric and other cumulative advantage processes",
1781:
Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive
Digraphs, Transitive Closures and Reductions",
303:
of a DAG is the graph with the most edges that has the same reachability relation as the DAG. It has an edge
1972:
1584:
1455:
1126:
3287:, Encyclopedia of Mathematics and its Applications, vol. 105, Cambridge University Press, p. 18,
353:
as its reachability relation. In this way, every finite partially ordered set can be represented as a DAG.
3232:
2886:
1422:
1410:
1187:
543:(without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is
3227:
Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs",
97:
58:
2372:
Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.
1596:
that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.
979:, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is
3184:
3049:
3010:, Mathematical surveys and monographs, vol. 152, American Mathematical Society, pp. 93–94,
2969:
2336:
Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems",
2104:
2008:
1865:
Bender, Edward A.; Williamson, S. Gill (2005), "Example 26 (Linear extensions – topological sorts)",
1753:
1418:
1245:
1215:
1211:
1118:
1102:
1027:
945:
505:
369:
70:
1984:
3237:
2725:
1293:
1231:
1171:
1122:
972:
918:
882:
877:
830:
762:
562:
448:
444:
109:
101:
62:
2488:
356:
3393:
3352:
3260:
3174:
3147:
3129:
3102:
3032:
2915:
2435:
2189:
2157:
2054:
1998:
1670:
1488:
1253:
1031:
894:
885:
is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in
464:
325:
of the DAG, and may therefore be thought of as a direct translation of the reachability relation
300:
2754:
792:, a DAG in which the subgraph reachable from any vertex induces an undirected tree (e.g. in red)
2461:
1491:, which traces the citation links and suggests the most significant citation chains in a given
3415:
3383:
3288:
3250:
3210:
3065:
3040:
3011:
2977:
2942:
2905:
2867:
2787:
2781:
2760:
2733:
2721:
2696:
2669:
2635:
2629:
2608:
2602:
2581:
2548:
2542:
2521:
2515:
2494:
2467:
2425:
2262:
2244:
2169:
2163:
2122:
2044:
1940:
1919:
1872:
1866:
1845:
1839:
1815:
1788:
1761:
1726:
1696:
1650:
1620:
1467:
1377:
1365:
1357:
1329:
712:
525:
391:
3282:
3005:
2963:
2690:
2077:
1809:
1782:
1747:
1690:
3375:
3344:
3317:
3242:
3200:
3192:
3139:
3094:
3057:
2897:
2857:
2847:
2820:
2663:
2573:
2417:
2347:
2230:
2208:
2100:
2034:
1720:
1588:
1560:
1522:
1515:
1507:
1499:
1459:
1316:
1286:
1167:
988:
976:
960:
740:
513:
364:
representing the partial order of set inclusion (⊆) among the subsets of a three-element set
38:
3165:
Evans, T.S.; Calmon, L.; Vasiliauskaite, V. (2020), "The
Longest Path in the Price Model",
2941:, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 845–854,
2359:
2258:
2355:
2254:
1944:
1695:, Cambridge Computer Science Texts, vol. 14, Cambridge University Press, p. 27,
1479:
1463:
1090:
1084:
758:
732:
282:. Both of these DAGs produce the same partial order, in which the vertices are ordered as
3188:
3053:
2973:
2012:
1757:
3321:
3308:
Lee, C. Y. (1959), "Representation of switching circuits by binary-decision programs",
3205:
2862:
2112:
1915:
1569:
1503:
1492:
1471:
1450:
1426:
720:
105:
50:
2939:
Proceedings of the
Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01)
1649:, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, pp. 32–34,
1437:. The final triangle reached in this path must be the Delaunay triangle that contains
1150:
Directed acyclic graph representations of partial orderings have many applications in
3442:
2997:
2655:
2226:
2212:
2026:
1593:
1403:
1361:
1114:
421:
417:
361:
184:
3419:
3397:
3356:
3264:
3151:
2919:
2692:
Probabilistic
Boolean Networks: The Modeling and Control of Gene Regulatory Networks
2439:
2058:
1814:, Algorithms and Computation in Mathematics, vol. 5, Springer, pp. 92–93,
1201:
A somewhat different DAG-based formulation of scheduling constraints is used by the
983:
to find. An arbitrary directed graph may also be transformed into a DAG, called its
437:
3106:
3001:
2717:
2659:
2281:
1980:
1968:
1907:
1896:
1716:
1333:
782:
482:
180:
121:
34:
2934:
2193:
2029:; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure",
1352:
1193:
951:
463:
Adding the red edges to the blue directed acyclic graph produces another DAG, the
457:
3231:, Lecture Notes in Computer Science, vol. 1264, Springer, pp. 116–129,
3061:
2838:
Kirkpatrick, Bonnie B. (April 2011), "Haplotypes versus genotypes on pedigrees",
1300:. An example of this type of directed acyclic graph are those encountered in the
3278:
2965:
Architecture and
Methods for Flexible Content Management in Peer-to-Peer Systems
2933:
Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001),
2901:
2073:
1976:
1385:
1381:
1372:
1321:
1301:
1297:
1249:
1178:
1163:
1159:
1155:
1068:
910:
886:
728:
54:
30:
3196:
1034:
to test reachability from each vertex. Alternatively, it can be solved in time
2824:
2577:
2108:
1235:
724:
702:{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.}
3246:
2266:
3424:
3348:
3143:
3007:
Combinatorial
Geometry and Its Algorithmic Applications: The Alcalá Lectures
2808:
2351:
1949:
1871:, Dover Books on Computer Science, Courier Dover Publications, p. 142,
1564:
it would take to list out all of the sequences separately. For example, the
1475:
1406:
1312:
996:
890:
817:
789:
3214:
3098:
3069:
2871:
2852:
2568:
Dennis, Jack B. (1974), "First version of a data flow procedure language",
1315:
between the events, we will have a directed acyclic graph. For instance, a
2421:
2039:
1583:
The same idea of using a DAG to represent a family of paths occurs in the
1429:
queries to be answered efficiently: to find the location of a query point
859:
the edges of an undirected tree away from a particular vertex, called the
512:
The family of topological orderings of a DAG is the same as the family of
2239:. Series of Books in the Mathematical Sciences (1st ed.). New York:
1615:
Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs",
1260:
1183:
1151:
921:. Different total orders may lead to the same acyclic orientation, so an
901:
successfully orders all the vertices without meeting an error condition.
838:
805:
3379:
398:
of the DAG. It is a subgraph of the DAG, formed by discarding the edges
166:
2517:
What Every Engineer Should Know About Decision Making Under Uncertainty
2490:
The Compiler Design Handbook: Optimizations and Machine Code Generation
2031:
Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)
1134:
980:
2236:
Computers and Intractability: A Guide to the Theory of NP-Completeness
846:) is a multitree formed by orienting the edges of an undirected tree.
2572:, Lecture Notes in Computer Science, vol. 19, pp. 362–376,
2003:
932:
acyclic orientations. The number of acyclic orientations is equal to
108:, each edge has an orientation, from one vertex to another vertex. A
798:
3179:
2286:
Structural Models: An Introduction to the Theory of Directed Graphs
2076:(1987), "The recovery of causal poly-trees from statistical data",
145:
Reachability relation, transitive closure, and transitive reduction
3134:
1458:
who went on to produce the first model of a citation network, the
1351:
1192:
950:
154:
21:
20:
1749:
Loop Transformations for Restructuring Compilers: The Foundations
1895:
Robinson, R. W. (1973), "Counting labeled acyclic digraphs", in
1787:, Springer Monographs in Mathematics, Springer, pp. 36–39,
1577:
1483:
1305:
769:
preserves the property that all matrix coefficients are 0 or 1.
190:
on the vertices of the DAG. In this partial order, two vertices
252:
has the same reachability relation as the DAG with three edges
2695:, Society for Industrial and Applied Mathematics, p. 58,
2631:
Large-Scale Software Architecture: A Practical Guide using UML
1592:
binary decision diagrams can be viewed as compressed forms of
1396:
1239:
1838:; Wayne, Kevin (2011), "4,2,25 Unique topological ordering",
765:, its adjacency matrix must have a zero diagonal, so adding
408:
for which the DAG also contains a longer directed path from
2935:"Finding least common ancestors in directed acyclic graphs"
808:, a DAG formed by orienting the edges of an undirected tree
549:
528:
problem of counting directed acyclic graphs was studied by
3432:
3372:
Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)
2894:
IEEE Symposium on Information Visualization (INFOVIS 2005)
909:
Any undirected graph may be made into a DAG by choosing a
1267:
efficiently. At a higher level of code organization, the
971:
Any directed graph may be made into a DAG by removing a
3086:
Journal of the American Society for Information Science
1725:, Monographs in Computer Science, Springer, p. 9,
1121:
from a given starting vertex in DAGs in linear time by
753:
is a (0,1) matrix with all eigenvalues positive, where
716:
3335:
Akers, Sheldon B. (1978), "Binary decision diagrams",
113:
acyclic graph is a directed graph that has no cycles.
1525:
573:
76:
Directed acyclic graphs are sometimes instead called
1985:"Acyclic digraphs and eigenvalues of (0,1)-matrices"
1645:
Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs",
345:
is automatically a transitively closed DAG, and has
1230:For instance, in electronic circuit design, static
337:, the graph that has a vertex for every element of
2887:"Interactive visualization of genealogical graphs"
1844:(4th ed.), Addison-Wesley, pp. 598–599,
1543:
1234:blocks can be represented as an acyclic system of
701:
649:
636:
2323:
2284:; Norman, Robert Z.; Cartwright, Dorwin (1965),
1692:Simulation Techniques for Discrete Event Systems
1158:after one of the cells has been changed, or the
2689:Shmulevich, Ilya; Dougherty, Edward R. (2010),
2414:23rd Australian Software Engineering Conference
208:exactly when there exists a directed path from
1559:Directed acyclic graphs may also be used as a
1304:though in this case the graphs considered are
1123:processing the vertices in a topological order
967:of the blue graph into a single yellow vertex.
547:1, 1, 3, 25, 543, 29281, 3781503, … (sequence
1784:Digraphs: Theory, Algorithms and Applications
1647:Digraphs: Theory, Algorithms and Applications
1190:for low-level computer program optimization.
1056:; this is a theoretical improvement over the
1054:exponent for matrix multiplication algorithms
467:of the blue graph. For each red or blue edge
8:
3374:, New York, NY, USA: ACM, pp. 348–356,
2132:Section 22.4, Topological sort, pp. 549–552.
1384:descent (mother-daughter relationships) and
1248:languages describe systems of operations on
1133:, and longest paths in arbitrary graphs are
1007:The transitive closure of a given DAG, with
999:, and its condensation is the graph itself.
959:of the blue directed graph. It is formed by
2493:(2nd ed.), CRC Press, pp. 19–39,
2121:(2nd ed.), MIT Press and McGraw-Hill,
1502:is too simple to be a realistic model of a
1003:Transitive closure and transitive reduction
3031:Price, Derek J. de Solla (July 30, 1965),
2885:McGuffin, M. J.; Balakrishnan, R. (2005),
2451:
2449:
2144:
1162:of a piece of computer software after its
341:and an edge for every pair of elements in
3236:
3204:
3178:
3133:
2861:
2851:
2730:Probabilistic Networks and Expert Systems
2601:Touati, Sid; de Dinechin, Benoit (2014),
2466:(2nd ed.), CRC Press, p. 1181,
2271:, Problems GT7 and GT8, pp. 191–192.
2038:
2002:
1746:Banerjee, Utpal (1993), "Exercise 2(c)",
1524:
1341:
955:The yellow directed acyclic graph is the
684:
659:
648:
635:
633:
621:
602:
591:
578:
572:
2809:"Causal diagrams for empirical research"
2628:Garland, Jeff; Anthony, Richard (2003),
719:proved, that the same numbers count the
529:
355:
128:when there exists a path that starts at
2487:Srikant, Y. N.; Shankar, Priti (2007),
2095:
2093:
1890:
1888:
1604:
1203:program evaluation and review technique
489:: there exists a blue path starting at
2783:Encyclopedia of Epidemiology, Volume 1
2668:, Oxford University Press, p. 4,
2634:, John Wiley & Sons, p. 215,
2607:, John Wiley & Sons, p. 123,
2399:
2311:
2299:
2140:
2138:
1901:New Directions in the Theory of Graphs
1868:A Short Course in Discrete Mathematics
1640:
1638:
1636:
1610:
1608:
1302:causal set approach to quantum gravity
16:Directed graph with no directed cycles
1722:The Design and Analysis of Algorithms
1675:Graph theory: an algorithmic approach
1166:has been changed. In this context, a
561:These numbers may be computed by the
7:
2288:, John Wiley & Sons, p. 63
1619:, John Wiley and Son, p. 118,
872:Topological sorting and recognition
447:of a directed acyclic graph: every
25:Example of a directed acyclic graph
3435:– an online tool for creating DAGs
3322:10.1002/j.1538-7305.1959.tb01585.x
2756:The Technology Management Handbook
1903:, Academic Press, pp. 239–273
1677:, Academic Press, pp. 170–174
1015:edges, may be constructed in time
925:-vertex graph can have fewer than
640:
120:of a directed graph is said to be
14:
2456:Gross, Jonathan L.; Yellen, Jay;
1177:For instance, when one cell of a
2840:Algorithms for Molecular Biology
2194:"Acyclic orientations of graphs"
1265:common subexpression elimination
797:
781:
456:
436:
183:of a DAG can be formalized as a
165:
153:
3033:"Networks of Scientific Papers"
1811:Graphs, Networks and Algorithms
905:Construction from cyclic graphs
321:) in the reachability relation
3337:IEEE Transactions on Computers
3284:Applied Combinatorics on Words
3229:Combinatorial Pattern Matching
2759:, CRC Press, p. 9-7,
2728:(1999), "3.2.1 Moralization",
2324:Bang-Jensen & Gutin (2008)
2168:, Springer, pp. 179–181,
1538:
1532:
1360:, with many marriages between
1269:acyclic dependencies principle
675:
663:
618:
608:
1:
3310:Bell System Technical Journal
2604:Advanced Backend Optimization
1617:Graphs: Theory and Algorithms
1348:Genealogy and version history
993:strongly connected components
394:of the reachability relation
3062:10.1126/science.149.3683.510
2732:, Springer, pp. 31–33,
2213:10.1016/0012-365X(73)90108-8
1990:Journal of Integer Sequences
1413:, the algorithm maintains a
1393:distributed revision control
1186:for program compilation and
965:strongly connected component
761:. Because a DAG cannot have
382:for every pair of vertices (
313:for every pair of vertices (
3122:Journal of Complex Networks
2902:10.1109/INFVIS.2005.1532124
2541:Sapatnekar, Sachin (2004),
2390:Cormen et al. 2001, p. 966.
2165:The Algorithm Design Manual
1910:; Palmer, Edgar M. (1973),
1808:Jungnickel, Dieter (2012),
1566:directed acyclic word graph
1275:Feedforward neural networks
1214:in this DAG represents the
1097:, such that no edges leave
3470:
3197:10.1038/s41598-020-67421-8
2520:, CRC Press, p. 160,
2162:Skiena, Steven S. (2009),
2118:Introduction to Algorithms
1284:
1082:
917:of the edges is called an
875:
823:strongly unambiguous graph
773:Related families of graphs
541: = 0, 1, 2, 3, …
216:in the DAG; that is, when
57:. That is, it consists of
2753:Dorf, Richard C. (1998),
2578:10.1007/3-540-06859-7_145
2547:, Springer, p. 133,
2241:W. H. Freeman and Company
1391:The version history of a
1210:to perform the task. The
520:Combinatorial enumeration
3247:10.1007/3-540-63220-4_55
2968:, Springer, p. 59,
2780:Boslaugh, Sarah (2008),
2463:Handbook of Graph Theory
2416:, IEEE, pp. 48–57,
1945:"Weisstein's Conjecture"
1752:, Springer, p. 19,
1222:Data processing networks
855:is a polytree formed by
743:of a DAG if and only if
532:. The number of DAGs on
172:Its transitive reduction
3454:Directed acyclic graphs
3349:10.1109/TC.1978.1675141
2825:10.1093/biomet/82.4.669
2726:Spiegelhalter, David J.
2352:10.1287/mnsc.22.11.1268
1585:binary decision diagram
1456:Derek J. de Solla Price
1376:father's side) causing
140:Mathematical properties
78:acyclic directed graphs
3099:10.1002/asi.4630270505
2962:Bartlang, Udo (2010),
2853:10.1186/1748-7188-6-10
2514:Wang, John X. (2002),
1561:compact representation
1545:
1544:{\displaystyle \ln(n)}
1423:Delaunay triangulation
1419:randomized incremental
1411:computational geometry
1369:
1198:
1188:instruction scheduling
1131:Bellman–Ford algorithm
968:
867:Computational problems
703:
607:
536:labeled vertices, for
365:
43:directed acyclic graph
26:
3144:10.1093/comnet/cnu039
2807:Pearl, Judea (1995),
2786:, SAGE, p. 255,
2722:Lauritzen, Steffen L.
2570:Programming Symposium
2422:10.1109/ASWEC.2014.15
2105:Leiserson, Charles E.
2040:10.1145/191666.191778
1912:Graphical Enumeration
1546:
1512:Barabási–Albert model
1355:
1306:transitively complete
1277:are another example.
1196:
1050: < 2.373
954:
863:of the arborescence.
704:
587:
359:
181:reachability relation
71:topologically ordered
24:
2201:Discrete Mathematics
2033:, pp. 330–336,
1689:Mitrani, I. (1982),
1523:
1484:transitive reduction
1342:topological ordering
1246:Dataflow programming
1127:Dijkstra's algorithm
1103:maximum flow problem
1028:breadth-first search
948:of the given graph.
946:chromatic polynomial
571:
506:topological ordering
445:topological ordering
428:Topological ordering
370:transitive reduction
124:from another vertex
3380:10.1145/37888.37941
3189:2020NatSR..1010503E
3054:1965Sci...149..510D
2974:2010aamf.book.....B
2716:Cowell, Robert G.;
2190:Stanley, Richard P.
2013:2004JIntS...7...33M
1758:1993ltfr.book.....B
1671:Christofides, Nicos
1462:. In this case the
1356:Family tree of the
1232:combinational logic
1172:circular dependency
973:feedback vertex set
919:acyclic orientation
883:Topological sorting
878:Topological sorting
717:McKay et al. (2004)
563:recurrence relation
3416:Weisstein, Eric W.
3167:Scientific Reports
2896:, pp. 16–23,
2339:Management Science
2158:depth-first search
2085:, pp. 222–228
1971:; Wanless, I. M.;
1941:Weisstein, Eric W.
1541:
1489:main path analysis
1370:
1254:parallel algorithm
1199:
1032:depth-first search
969:
895:depth-first search
699:
465:transitive closure
366:
301:transitive closure
228:is reachable from
27:
3420:"Acyclic Digraph"
3389:978-0-8186-0781-3
3256:978-3-540-63220-7
3048:(3683): 510–515,
3017:978-0-8218-7533-9
2983:978-3-8348-9645-2
2948:978-0-89871-490-6
2911:978-0-7803-9464-3
2793:978-1-4129-2816-8
2766:978-0-8493-8577-3
2739:978-0-387-98767-5
2702:978-0-89871-692-4
2675:978-0-19-803928-0
2614:978-1-118-64894-0
2587:978-3-540-06859-4
2554:978-1-4020-7671-8
2527:978-0-8247-4373-4
2500:978-1-4200-4383-9
2473:978-1-4398-8018-0
2431:978-1-4799-3149-1
2346:(11): 1268–1272,
2231:Johnson, David S.
2227:Garey, Michael R.
2175:978-1-84800-070-4
2145:Jungnickel (2012)
2109:Rivest, Ronald L.
2101:Cormen, Thomas H.
2027:Furnas, George W.
2016:, Article 04.3.3.
1925:978-0-12-324245-7
1878:978-0-486-43946-4
1851:978-0-13-276256-4
1836:Sedgewick, Robert
1821:978-3-642-32278-5
1794:978-1-84800-998-1
1767:978-0-7923-9318-4
1732:978-0-387-97687-7
1656:978-1-84800-997-4
1626:978-0-471-51356-8
1514:. However, since
1468:citation analysis
1378:pedigree collapse
1366:pedigree collapse
1358:Ptolemaic dynasty
1330:influence diagram
1281:Causal structures
897:graph traversal.
715:conjectured, and
713:Eric W. Weisstein
647:
526:graph enumeration
514:linear extensions
392:covering relation
3461:
3429:
3428:
3402:
3400:
3367:
3361:
3359:
3332:
3326:
3324:
3305:
3299:
3297:
3275:
3269:
3267:
3240:
3224:
3218:
3217:
3208:
3182:
3162:
3156:
3154:
3137:
3117:
3111:
3109:
3080:
3074:
3072:
3037:
3028:
3022:
3020:
2994:
2988:
2986:
2959:
2953:
2951:
2930:
2924:
2922:
2891:
2882:
2876:
2874:
2865:
2855:
2835:
2829:
2827:
2804:
2798:
2796:
2777:
2771:
2769:
2750:
2744:
2742:
2718:Dawid, A. Philip
2713:
2707:
2705:
2686:
2680:
2678:
2652:
2646:
2644:
2625:
2619:
2617:
2598:
2592:
2590:
2565:
2559:
2557:
2538:
2532:
2530:
2511:
2505:
2503:
2484:
2478:
2476:
2453:
2444:
2442:
2409:
2403:
2397:
2391:
2388:
2382:
2379:
2373:
2370:
2364:
2362:
2333:
2327:
2321:
2315:
2309:
2303:
2297:
2291:
2289:
2278:
2272:
2270:
2223:
2217:
2215:
2198:
2186:
2180:
2178:
2154:
2148:
2142:
2133:
2131:
2097:
2088:
2086:
2084:
2072:Rebane, George;
2069:
2063:
2061:
2042:
2023:
2017:
2015:
2006:
1977:Sloane, N. J. A.
1961:
1955:
1954:
1953:
1936:
1930:
1928:
1904:
1892:
1883:
1881:
1862:
1856:
1854:
1832:
1826:
1824:
1805:
1799:
1797:
1778:
1772:
1770:
1743:
1737:
1735:
1713:
1707:
1705:
1686:
1680:
1678:
1667:
1661:
1659:
1642:
1631:
1629:
1612:
1589:truth assignment
1555:Data compression
1550:
1548:
1547:
1542:
1504:citation network
1480:network analysis
1472:Court judgements
1440:
1436:
1432:
1395:system, such as
1380:. The graphs of
1317:Bayesian network
1313:causal relations
1287:Bayesian network
1168:dependency graph
1066:
1051:
1044:
1026:by using either
1025:
1014:
1010:
977:feedback arc set
943:
939:
931:
924:
801:
785:
768:
756:
752:
741:adjacency matrix
738:
708:
706:
705:
700:
695:
694:
679:
678:
654:
653:
652:
639:
632:
631:
606:
601:
583:
582:
552:
542:
535:
496:
492:
488:
480:
476:
460:
440:
415:
411:
407:
397:
389:
385:
381:
352:
344:
340:
336:
328:
324:
320:
316:
312:
295:
281:
271:
261:
251:
241:
231:
227:
223:
219:
215:
211:
207:
197:
193:
189:
169:
157:
135:
131:
127:
119:
82:acyclic digraphs
39:computer science
3469:
3468:
3464:
3463:
3462:
3460:
3459:
3458:
3449:Directed graphs
3439:
3438:
3414:
3413:
3410:
3405:
3390:
3369:
3368:
3364:
3334:
3333:
3329:
3307:
3306:
3302:
3295:
3277:
3276:
3272:
3257:
3226:
3225:
3221:
3164:
3163:
3159:
3119:
3118:
3114:
3082:
3081:
3077:
3035:
3030:
3029:
3025:
3018:
2996:
2995:
2991:
2984:
2961:
2960:
2956:
2949:
2932:
2931:
2927:
2912:
2889:
2884:
2883:
2879:
2837:
2836:
2832:
2806:
2805:
2801:
2794:
2779:
2778:
2774:
2767:
2752:
2751:
2747:
2740:
2715:
2714:
2710:
2703:
2688:
2687:
2683:
2676:
2665:Causal Learning
2654:
2653:
2649:
2642:
2627:
2626:
2622:
2615:
2600:
2599:
2595:
2588:
2567:
2566:
2562:
2555:
2540:
2539:
2535:
2528:
2513:
2512:
2508:
2501:
2486:
2485:
2481:
2474:
2455:
2454:
2447:
2432:
2411:
2410:
2406:
2398:
2394:
2389:
2385:
2380:
2376:
2371:
2367:
2335:
2334:
2330:
2322:
2318:
2310:
2306:
2298:
2294:
2280:
2279:
2275:
2251:
2225:
2224:
2220:
2196:
2188:
2187:
2183:
2176:
2161:
2155:
2151:
2143:
2136:
2129:
2113:Stein, Clifford
2099:
2098:
2091:
2082:
2071:
2070:
2066:
2051:
2025:
2024:
2020:
1963:
1962:
1958:
1939:
1938:
1937:
1933:
1926:
1906:
1894:
1893:
1886:
1879:
1864:
1863:
1859:
1852:
1834:
1833:
1829:
1822:
1807:
1806:
1802:
1795:
1780:
1779:
1775:
1768:
1745:
1744:
1740:
1733:
1715:
1714:
1710:
1703:
1688:
1687:
1683:
1669:
1668:
1664:
1657:
1644:
1643:
1634:
1627:
1614:
1613:
1606:
1602:
1557:
1521:
1520:
1482:. For instance
1447:
1445:Citation graphs
1438:
1434:
1430:
1362:close relatives
1350:
1289:
1283:
1224:
1148:
1143:
1111:
1109:Path algorithms
1091:closure problem
1087:
1085:Closure problem
1081:
1079:Closure problem
1057:
1046:
1035:
1016:
1012:
1008:
1005:
941:
933:
926:
922:
907:
893:numbering of a
880:
874:
869:
842:(also called a
831:undirected tree
821:(also called a
813:
812:
811:
810:
809:
802:
794:
793:
786:
775:
766:
759:identity matrix
754:
744:
736:
731:. The proof is
680:
655:
634:
617:
574:
569:
568:
548:
537:
533:
530:Robinson (1973)
522:
502:
501:
500:
499:
498:
494:
490:
486:
478:
468:
461:
453:
452:
441:
430:
413:
409:
399:
395:
387:
383:
373:
346:
342:
338:
330:
326:
322:
318:
314:
304:
283:
273:
263:
253:
243:
233:
229:
225:
221:
217:
213:
209:
199:
198:are ordered as
195:
191:
187:
177:
176:
175:
174:
173:
170:
162:
161:
158:
147:
142:
133:
129:
125:
117:
90:
55:directed cycles
33:, particularly
17:
12:
11:
5:
3467:
3465:
3457:
3456:
3451:
3441:
3440:
3437:
3436:
3430:
3409:
3408:External links
3406:
3404:
3403:
3388:
3362:
3343:(6): 509–516,
3327:
3316:(4): 985–999,
3300:
3293:
3270:
3255:
3238:10.1.1.53.6273
3219:
3157:
3128:(2): 189–203,
3112:
3093:(5): 292–306,
3075:
3023:
3016:
2989:
2982:
2954:
2947:
2925:
2910:
2877:
2830:
2819:(4): 669–709,
2799:
2792:
2772:
2765:
2745:
2738:
2708:
2701:
2681:
2674:
2656:Gopnik, Alison
2647:
2640:
2620:
2613:
2593:
2586:
2560:
2553:
2533:
2526:
2506:
2499:
2479:
2472:
2445:
2430:
2404:
2392:
2383:
2374:
2365:
2328:
2316:
2304:
2292:
2273:
2249:
2218:
2207:(2): 171–178,
2181:
2174:
2149:
2134:
2127:
2089:
2064:
2050:978-0897916509
2049:
2018:
1956:
1931:
1924:
1918:, p. 19,
1916:Academic Press
1884:
1877:
1857:
1850:
1827:
1820:
1800:
1793:
1773:
1766:
1738:
1731:
1708:
1701:
1681:
1662:
1655:
1632:
1625:
1603:
1601:
1598:
1594:decision trees
1570:data structure
1556:
1553:
1540:
1537:
1534:
1531:
1528:
1493:citation graph
1464:citation count
1451:citation graph
1446:
1443:
1427:point location
1421:algorithm for
1349:
1346:
1285:Main article:
1282:
1279:
1223:
1220:
1147:
1144:
1142:
1139:
1115:shortest paths
1110:
1107:
1083:Main article:
1080:
1077:
1004:
1001:
906:
903:
876:Main article:
873:
870:
868:
865:
803:
796:
795:
787:
780:
779:
778:
777:
776:
774:
771:
723:for which all
721:(0,1) matrices
710:
709:
698:
693:
690:
687:
683:
677:
674:
671:
668:
665:
662:
658:
651:
646:
643:
638:
630:
627:
624:
620:
616:
613:
610:
605:
600:
597:
594:
590:
586:
581:
577:
559:
558:
521:
518:
493:and ending at
462:
455:
454:
442:
435:
434:
433:
432:
431:
429:
426:
418:graph drawings
171:
164:
163:
159:
152:
151:
150:
149:
148:
146:
143:
141:
138:
106:directed graph
89:
86:
51:directed graph
15:
13:
10:
9:
6:
4:
3:
2:
3466:
3455:
3452:
3450:
3447:
3446:
3444:
3434:
3431:
3427:
3426:
3421:
3417:
3412:
3411:
3407:
3399:
3395:
3391:
3385:
3381:
3377:
3373:
3366:
3363:
3358:
3354:
3350:
3346:
3342:
3338:
3331:
3328:
3323:
3319:
3315:
3311:
3304:
3301:
3296:
3294:9780521848022
3290:
3286:
3285:
3280:
3274:
3271:
3266:
3262:
3258:
3252:
3248:
3244:
3239:
3234:
3230:
3223:
3220:
3216:
3212:
3207:
3202:
3198:
3194:
3190:
3186:
3181:
3176:
3172:
3168:
3161:
3158:
3153:
3149:
3145:
3141:
3136:
3131:
3127:
3123:
3116:
3113:
3108:
3104:
3100:
3096:
3092:
3088:
3087:
3079:
3076:
3071:
3067:
3063:
3059:
3055:
3051:
3047:
3043:
3042:
3034:
3027:
3024:
3019:
3013:
3009:
3008:
3003:
3002:Sharir, Micha
2999:
2993:
2990:
2985:
2979:
2975:
2971:
2967:
2966:
2958:
2955:
2950:
2944:
2940:
2936:
2929:
2926:
2921:
2917:
2913:
2907:
2903:
2899:
2895:
2888:
2881:
2878:
2873:
2869:
2864:
2859:
2854:
2849:
2845:
2841:
2834:
2831:
2826:
2822:
2818:
2814:
2810:
2803:
2800:
2795:
2789:
2785:
2784:
2776:
2773:
2768:
2762:
2758:
2757:
2749:
2746:
2741:
2735:
2731:
2727:
2723:
2719:
2712:
2709:
2704:
2698:
2694:
2693:
2685:
2682:
2677:
2671:
2667:
2666:
2661:
2660:Schulz, Laura
2657:
2651:
2648:
2643:
2641:9780470856383
2637:
2633:
2632:
2624:
2621:
2616:
2610:
2606:
2605:
2597:
2594:
2589:
2583:
2579:
2575:
2571:
2564:
2561:
2556:
2550:
2546:
2545:
2537:
2534:
2529:
2523:
2519:
2518:
2510:
2507:
2502:
2496:
2492:
2491:
2483:
2480:
2475:
2469:
2465:
2464:
2459:
2452:
2450:
2446:
2441:
2437:
2433:
2427:
2423:
2419:
2415:
2408:
2405:
2401:
2400:Skiena (2009)
2396:
2393:
2387:
2384:
2378:
2375:
2369:
2366:
2361:
2357:
2353:
2349:
2345:
2341:
2340:
2332:
2329:
2325:
2320:
2317:
2313:
2312:Skiena (2009)
2308:
2305:
2301:
2300:Skiena (2009)
2296:
2293:
2287:
2283:
2282:Harary, Frank
2277:
2274:
2268:
2264:
2260:
2256:
2252:
2250:9780716710455
2246:
2242:
2238:
2237:
2232:
2228:
2222:
2219:
2214:
2210:
2206:
2202:
2195:
2191:
2185:
2182:
2177:
2171:
2167:
2166:
2159:
2153:
2150:
2146:
2141:
2139:
2135:
2130:
2128:0-262-03293-7
2124:
2120:
2119:
2114:
2110:
2106:
2102:
2096:
2094:
2090:
2081:
2080:
2075:
2068:
2065:
2060:
2056:
2052:
2046:
2041:
2036:
2032:
2028:
2022:
2019:
2014:
2010:
2005:
2000:
1996:
1992:
1991:
1986:
1982:
1978:
1974:
1973:Oggier, F. E.
1970:
1966:
1960:
1957:
1952:
1951:
1946:
1942:
1935:
1932:
1927:
1921:
1917:
1913:
1909:
1908:Harary, Frank
1902:
1898:
1891:
1889:
1885:
1880:
1874:
1870:
1869:
1861:
1858:
1853:
1847:
1843:
1842:
1837:
1831:
1828:
1823:
1817:
1813:
1812:
1804:
1801:
1796:
1790:
1786:
1785:
1777:
1774:
1769:
1763:
1759:
1755:
1751:
1750:
1742:
1739:
1734:
1728:
1724:
1723:
1718:
1717:Kozen, Dexter
1712:
1709:
1704:
1702:9780521282826
1698:
1694:
1693:
1685:
1682:
1676:
1672:
1666:
1663:
1658:
1652:
1648:
1641:
1639:
1637:
1633:
1628:
1622:
1618:
1611:
1609:
1605:
1599:
1597:
1595:
1590:
1586:
1581:
1579:
1575:
1571:
1567:
1562:
1554:
1552:
1535:
1529:
1526:
1517:
1516:Price's model
1513:
1509:
1505:
1501:
1496:
1494:
1490:
1485:
1481:
1477:
1473:
1469:
1465:
1461:
1457:
1452:
1444:
1442:
1428:
1424:
1420:
1416:
1412:
1408:
1405:
1400:
1398:
1394:
1389:
1387:
1383:
1379:
1374:
1367:
1363:
1359:
1354:
1347:
1345:
1343:
1337:
1335:
1331:
1327:
1323:
1318:
1314:
1309:
1307:
1303:
1299:
1295:
1288:
1280:
1278:
1276:
1272:
1270:
1266:
1262:
1257:
1255:
1251:
1247:
1243:
1241:
1237:
1233:
1228:
1221:
1219:
1217:
1216:critical path
1213:
1208:
1204:
1195:
1191:
1189:
1185:
1180:
1175:
1173:
1169:
1165:
1161:
1157:
1153:
1145:
1140:
1138:
1136:
1132:
1128:
1124:
1120:
1119:longest paths
1116:
1108:
1106:
1104:
1100:
1096:
1092:
1086:
1078:
1076:
1072:
1070:
1064:
1060:
1055:
1049:
1042:
1038:
1033:
1029:
1023:
1019:
1011:vertices and
1002:
1000:
998:
994:
990:
986:
982:
978:
974:
966:
962:
958:
953:
949:
947:
937:
929:
920:
916:
912:
904:
902:
898:
896:
892:
888:
884:
879:
871:
866:
864:
862:
858:
854:
853:
847:
845:
844:directed tree
841:
840:
834:
832:
828:
824:
820:
819:
807:
800:
791:
784:
772:
770:
764:
760:
751:
748: +
747:
742:
734:
730:
727:are positive
726:
722:
718:
714:
696:
691:
688:
685:
681:
672:
669:
666:
660:
656:
644:
641:
628:
625:
622:
614:
611:
603:
598:
595:
592:
588:
584:
579:
575:
567:
566:
565:
564:
556:
551:
546:
545:
544:
540:
531:
527:
519:
517:
515:
510:
507:
484:
475:
471:
466:
459:
450:
446:
439:
427:
425:
423:
422:Hasse diagram
419:
406:
402:
393:
380:
376:
371:
363:
362:Hasse diagram
358:
354:
350:
334:
311:
307:
302:
297:
294:
290:
286:
280:
276:
270:
266:
260:
256:
250:
246:
240:
236:
206:
202:
186:
185:partial order
182:
168:
156:
144:
139:
137:
123:
114:
111:
107:
103:
99:
96:is formed by
95:
87:
85:
83:
79:
74:
72:
68:
65:(also called
64:
60:
56:
52:
48:
44:
40:
36:
32:
23:
19:
3423:
3371:
3365:
3340:
3336:
3330:
3313:
3309:
3303:
3283:
3279:Lothaire, M.
3273:
3228:
3222:
3173:(1): 10503,
3170:
3166:
3160:
3125:
3121:
3115:
3090:
3084:
3078:
3045:
3039:
3026:
3006:
2992:
2964:
2957:
2938:
2928:
2893:
2880:
2843:
2839:
2833:
2816:
2812:
2802:
2782:
2775:
2755:
2748:
2729:
2711:
2691:
2684:
2664:
2650:
2630:
2623:
2603:
2596:
2569:
2563:
2543:
2536:
2516:
2509:
2489:
2482:
2462:
2413:
2407:
2395:
2386:
2377:
2368:
2343:
2337:
2331:
2319:
2307:
2295:
2285:
2276:
2234:
2221:
2204:
2200:
2184:
2164:
2152:
2147:, pp. 50–51.
2117:
2078:
2074:Pearl, Judea
2067:
2030:
2021:
2004:math/0310423
1994:
1988:
1969:Royle, G. F.
1965:McKay, B. D.
1959:
1948:
1934:
1911:
1900:
1867:
1860:
1840:
1830:
1810:
1803:
1783:
1776:
1748:
1741:
1721:
1711:
1691:
1684:
1674:
1665:
1646:
1616:
1582:
1558:
1497:
1448:
1414:
1401:
1390:
1373:Family trees
1371:
1338:
1334:epidemiology
1325:
1310:
1298:causal loops
1290:
1273:
1258:
1250:data streams
1244:
1229:
1225:
1212:longest path
1200:
1176:
1160:object files
1149:
1141:Applications
1112:
1098:
1094:
1088:
1073:
1069:dense graphs
1062:
1058:
1047:
1040:
1036:
1021:
1017:
1006:
991:each of its
985:condensation
970:
957:condensation
935:
927:
908:
899:
881:
860:
852:arborescence
850:
848:
843:
837:
835:
826:
822:
816:
814:
757:denotes the
749:
745:
729:real numbers
711:
560:
538:
523:
511:
503:
473:
469:
404:
400:
378:
374:
367:
348:
332:
309:
305:
298:
292:
288:
284:
278:
274:
268:
264:
258:
254:
248:
244:
238:
234:
204:
200:
178:
132:and ends at
115:
91:
81:
77:
75:
66:
46:
42:
35:graph theory
28:
18:
2998:Pach, János
2458:Zhang, Ping
1905:. See also
1508:Price model
1500:Price model
1460:Price model
1454:Papers" by
1415:history DAG
1386:patrilineal
1382:matrilineal
1322:moral graph
1292:follow any
1236:logic gates
1179:spreadsheet
1164:source code
1156:spreadsheet
989:contracting
961:contracting
915:orientation
911:total order
887:linear time
735:: a matrix
725:eigenvalues
88:Definitions
31:mathematics
3443:Categories
3180:1903.03667
2846:(10): 10,
2813:Biometrika
1897:Harary, F.
1841:Algorithms
1600:References
1407:algorithms
1404:randomized
1207:milestones
1152:scheduling
1146:Scheduling
1067:bound for
763:self-loops
220:can reach
3425:MathWorld
3233:CiteSeerX
3135:1310.8224
2402:, p. 469.
2314:, p. 496.
2302:, p. 495.
2267:247570676
2115:(2001) ,
1950:MathWorld
1530:
1476:prior art
1261:compilers
1184:makefiles
1137:to find.
891:postorder
857:orienting
818:multitree
790:multitree
733:bijective
689:−
670:−
626:−
612:−
589:∑
483:reachable
390:) in the
122:reachable
116:A vertex
3398:14796451
3357:21028055
3281:(2005),
3265:17045308
3215:32601403
3152:10228152
3070:14325149
2920:15449409
2872:21504603
2662:(2007),
2460:(2013),
2440:17570052
2326:, p. 38.
2233:(1979).
2192:(1973),
2059:18710118
1983:(2004),
1981:Wilf, H.
1719:(1992),
1673:(1975),
1402:In many
1364:causing
1326:marrying
940:, where
839:polytree
827:mangrove
806:polytree
98:vertices
59:vertices
53:with no
3433:DAGitty
3206:7324613
3185:Bibcode
3107:8536863
3050:Bibcode
3041:Science
2970:Bibcode
2863:3102622
2360:0403596
2259:0519066
2009:Bibcode
1899:(ed.),
1754:Bibcode
1574:strings
1135:NP-hard
1129:or the
1052:is the
981:NP-hard
944:is the
553:in the
550:A003024
100:and by
49:) is a
3396:
3386:
3355:
3291:
3263:
3253:
3235:
3213:
3203:
3150:
3105:
3068:
3014:
2980:
2945:
2918:
2908:
2870:
2860:
2790:
2763:
2736:
2699:
2672:
2638:
2611:
2584:
2551:
2544:Timing
2524:
2497:
2470:
2438:
2428:
2358:
2265:
2257:
2247:
2172:
2125:
2057:
2047:
1997:: 33,
1922:
1875:
1848:
1818:
1791:
1764:
1729:
1699:
1653:
1623:
1510:, the
1045:where
739:is an
272:, and
37:, and
3394:S2CID
3353:S2CID
3261:S2CID
3175:arXiv
3148:S2CID
3130:arXiv
3103:S2CID
3036:(PDF)
2916:S2CID
2890:(PDF)
2436:S2CID
2197:(PDF)
2083:(PDF)
2055:S2CID
1999:arXiv
1568:is a
1449:In a
997:empty
987:, by
975:or a
963:each
938:(−1)|
825:or a
485:from
160:A DAG
102:edges
94:graph
63:edges
3384:ISBN
3341:C-27
3289:ISBN
3251:ISBN
3211:PMID
3066:PMID
3012:ISBN
2978:ISBN
2943:ISBN
2906:ISBN
2868:PMID
2788:ISBN
2761:ISBN
2734:ISBN
2697:ISBN
2670:ISBN
2636:ISBN
2609:ISBN
2582:ISBN
2549:ISBN
2522:ISBN
2495:ISBN
2468:ISBN
2426:ISBN
2263:OCLC
2245:ISBN
2170:ISBN
2156:For
2123:ISBN
2045:ISBN
1920:ISBN
1873:ISBN
1846:ISBN
1816:ISBN
1789:ISBN
1762:ISBN
1727:ISBN
1697:ISBN
1651:ISBN
1621:ISBN
1578:trie
1498:The
1294:path
1240:bits
1117:and
1089:The
861:root
555:OEIS
524:The
449:edge
420:. A
368:The
351:, ≤)
335:, ≤)
299:The
242:and
224:(or
194:and
179:The
110:path
67:arcs
61:and
41:, a
3376:doi
3345:doi
3318:doi
3243:doi
3201:PMC
3193:doi
3140:doi
3095:doi
3058:doi
3046:149
2898:doi
2858:PMC
2848:doi
2821:doi
2574:doi
2418:doi
2348:doi
2209:doi
2035:doi
1409:in
1397:Git
1259:In
1030:or
849:An
481:is
412:to
212:to
80:or
47:DAG
29:In
3445::
3422:,
3418:,
3392:,
3382:,
3351:,
3339:,
3314:38
3312:,
3259:,
3249:,
3241:,
3209:,
3199:,
3191:,
3183:,
3171:10
3169:,
3146:,
3138:,
3124:,
3101:,
3091:27
3089:,
3064:,
3056:,
3044:,
3038:,
3004:,
3000:;
2976:,
2937:,
2914:,
2904:,
2892:,
2866:,
2856:,
2842:,
2817:82
2815:,
2811:,
2724:;
2720:;
2658:;
2580:,
2448:^
2434:,
2424:,
2356:MR
2354:,
2344:22
2342:,
2261:.
2255:MR
2253:.
2243:.
2229:;
2203:,
2199:,
2137:^
2111:;
2107:;
2103:;
2092:^
2053:,
2043:,
2007:,
1993:,
1987:,
1979:;
1975:;
1967:;
1947:,
1943:,
1914:,
1887:^
1760:,
1635:^
1607:^
1551:.
1527:ln
1495:.
1470:.
1441:.
1105:.
1071:.
1063:mn
1022:mn
836:A
833:.
815:A
804:A
788:A
557:).
504:A
477:,
472:→
443:A
403:→
386:,
377:→
360:A
317:,
308:→
296:.
291:≤
287:≤
277:→
267:→
262:,
257:→
247:→
237:→
203:≤
92:A
84:.
3401:.
3378::
3360:.
3347::
3325:.
3320::
3298:.
3268:.
3245::
3195::
3187::
3177::
3155:.
3142::
3132::
3126:3
3110:.
3097::
3073:.
3060::
3052::
3021:.
2987:.
2972::
2952:.
2923:.
2900::
2875:.
2850::
2844:6
2828:.
2823::
2797:.
2770:.
2743:.
2706:.
2679:.
2645:.
2618:.
2591:.
2576::
2558:.
2531:.
2504:.
2477:.
2443:.
2420::
2363:.
2350::
2290:.
2269:.
2216:.
2211::
2205:5
2179:.
2087:.
2062:.
2037::
2011::
2001::
1995:7
1929:.
1882:.
1855:.
1825:.
1798:.
1771:.
1756::
1736:.
1706:.
1679:.
1660:.
1630:.
1539:)
1536:n
1533:(
1439:q
1435:q
1431:q
1368:.
1099:C
1095:C
1065:)
1061:(
1059:O
1048:ω
1043:)
1041:n
1039:(
1037:O
1024:)
1020:(
1018:O
1013:m
1009:n
942:χ
936:χ
934:|
930:!
928:n
923:n
767:I
755:I
750:I
746:A
737:A
697:.
692:k
686:n
682:a
676:)
673:k
667:n
664:(
661:k
657:2
650:)
645:k
642:n
637:(
629:1
623:k
619:)
615:1
609:(
604:n
599:1
596:=
593:k
585:=
580:n
576:a
539:n
534:n
497:.
495:v
491:u
487:u
479:v
474:v
470:u
414:v
410:u
405:v
401:u
396:≤
388:v
384:u
379:v
375:u
349:S
347:(
343:≤
339:S
333:S
331:(
327:≤
323:≤
319:v
315:u
310:v
306:u
293:w
289:v
285:u
279:w
275:u
269:w
265:v
259:v
255:u
249:w
245:v
239:v
235:u
230:u
226:v
222:v
218:u
214:v
210:u
205:v
201:u
196:v
192:u
188:≤
134:v
130:u
126:u
118:v
45:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.