Directed acyclic graph - Knowledge (XXG)

900:. 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 520:

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.

368: 449: 794: 1253:. 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. 469: 1205: 963: 427:. 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 1436:, 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 178: 1364: 1193:

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

810: 147:. 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. 166: 33: 1574:

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

1220:

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

1192:

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

1085:

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

519:

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

123:

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

1464:

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

1386:

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

1302:

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

911:

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

1602:

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,

1587:, 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 1263:, 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 84:, 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). 1319:. 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. 1350:

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

1112:. 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 1529:

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

1489:, 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 1274:, 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 1598:, 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 1410:, 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. 718: 1237:

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.

1136:, 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 1330:

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

1497:

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

1307:

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

1485:

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

1591:. 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. 435:

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.

1583:

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

1181:

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

3096: 1229:

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.

1185:, 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. 80:), 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 1517:

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

1165:

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

1064: 1343:, 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 840:) 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 1560: 1124:

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

1086:

the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.

462:

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.

1576: 1322:

Sometimes events are not associated with a specific physical time. Provided that pairs of events have a purely causal relationship, that is edges represent

1216:(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 565: 581: 1213: 340:

into graph-theoretic terms. The same method of translating partial orders into DAGs works more generally: for every finite partially ordered set

3398: 3265: 3026: 2992: 2957: 2920: 2802: 2775: 2748: 2711: 2684: 2623: 2596: 2563: 2536: 2509: 2482: 2440: 2184: 1934: 1887: 1860: 1846: 1830: 1803: 1776: 1741: 1665: 1635: 527:

of the reachability relation for the DAG, so any two graphs representing the same partial order have the same set of topological orders.

243:). However, different DAGs may give rise to the same reachability relation and the same partial order. For example, a DAG with two edges 1399:

descent (father-son relationships) are trees within this graph. Because no one can become their own ancestor, family trees are acyclic.

1428:

representing the version history of a geometric structure over the course of a sequence of changes to the structure. For instance in a

2059: 3303: 2650: 2259: 2171:

based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g.

2137: 1711: 1208:

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.

1355:, 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. 1104:

takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices

3464: 1335:

of a DAG is the undirected graph created by adding an (undirected) edge between all parents of the same vertex (sometimes called

1275: 115:

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

1444:

in the Delaunay triangulation, follow a path in the history DAG, at each step moving to the replacement triangle that contains

2423:

Al-Mutawa, H. A.; Dietrich, J.; Marsland, S.; McCartin, C. (2014), "On the shape of circular dependencies in Java programs",

1279: 1217: 1282:

states that the dependencies between modules or components of a large software system should form a directed acyclic graph.

1975: 1339:), and then replacing all directed edges by undirected edges. Another type of graph with a similar causal structure is an 1006:

into a single supervertex. When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are

1522: 2392:

Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.

2349: 2246: 2000: 1403: 1003: 975: 104: 3131:

Clough, James R.; Gollings, Jamie; Loach, Tamar V.; Evans, Tim S. (2015), "Transitive reduction of citation networks",

2468: 1477:

of a paper is just the in-degree of the corresponding vertex of the citation network. This is an important measure in

995: 967: 924:

for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting

862: 1267:

in which each operation is performed by a parallel process as soon as another set of inputs becomes available to it.

1141: 1347:, for instance, these diagrams are often used to estimate the expected value of different choices for intervention. 2127: 1285: 925: 867: 2251: 1584: 2090:

in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987

3459: 1249:

that computes a function of an input, where the input and output of the function are represented as individual

383:

of a DAG is the graph with the fewest edges that has the same reachability relation as the DAG. It has an edge

3381:

Friedman, S. J.; Supowit, K. J. (1987), "Finding the optimal variable ordering for binary decision diagrams",

3094:

Price, Derek J. de Solla (1976), "A general theory of bibliometric and other cumulative advantage processes",

1792:

Bang-Jensen, Jørgen; Gutin, Gregory Z. (2008), "2.3 Transitive Digraphs, Transitive Closures and Reductions",

314:

of a DAG is the graph with the most edges that has the same reachability relation as the DAG. It has an edge

1983: 1595: 1466: 1137: 3298:, Encyclopedia of Mathematics and its Applications, vol. 105, Cambridge University Press, p. 18, 364:

as its reachability relation. In this way, every finite partially ordered set can be represented as a DAG.

3243: 2897: 1433: 1421: 1198: 554:(without restrictions on the order in which these numbers appear in a topological ordering of the DAG) is 3238:

Crochemore, Maxime; Vérin, Renaud (1997), "Direct construction of compact directed acyclic word graphs",

108: 69: 2383:

Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.

1607:

that save space by allowing paths to rejoin when they agree on the results of all remaining decisions.

990:, a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is 3195: 3060: 3021:, Mathematical surveys and monographs, vol. 152, American Mathematical Society, pp. 93–94, 2980: 2347:

Picard, Jean-Claude (1976), "Maximal closure of a graph and applications to combinatorial problems",

2115: 2019: 1876:

Bender, Edward A.; Williamson, S. Gill (2005), "Example 26 (Linear extensions – topological sorts)",

1764: 1429: 1256: 1226: 1222: 1129: 1113: 1038: 956: 516: 380: 81: 1995: 3248: 2736: 1304: 1242: 1182: 1133: 983: 929: 893: 888: 841: 773: 573: 459: 455: 120: 112: 73: 2499: 367: 3404: 3363: 3271: 3185: 3158: 3140: 3113: 3043: 2926: 2446: 2200: 2168: 2065: 2009: 1681: 1499: 1264: 1042: 905: 896:

is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in

475: 336:

of the DAG, and may therefore be thought of as a direct translation of the reachability relation

311: 2765: 803:, a DAG in which the subgraph reachable from any vertex induces an undirected tree (e.g. in red) 2472: 1502:, which traces the citation links and suggests the most significant citation chains in a given 3426: 3394: 3299: 3261: 3221: 3076: 3051: 3022: 2988: 2953: 2916: 2878: 2798: 2792: 2771: 2744: 2732: 2707: 2680: 2646: 2640: 2619: 2613: 2592: 2559: 2553: 2532: 2526: 2505: 2478: 2436: 2273: 2255: 2180: 2174: 2133: 2055: 1951: 1930: 1883: 1877: 1856: 1850: 1826: 1799: 1772: 1737: 1707: 1661: 1631: 1478: 1388: 1376: 1368: 1340: 723: 536: 402: 3293: 3016: 2974: 2701: 2088: 1820: 1793: 1758: 1701: 3386: 3355: 3328: 3253: 3211: 3203: 3150: 3105: 3068: 2908: 2868: 2858: 2831: 2674: 2584: 2428: 2358: 2241: 2219: 2111: 2045: 1731: 1599: 1571: 1533: 1526: 1518: 1510: 1470: 1327: 1297: 1178: 999: 987: 971: 751: 524: 375:

representing the partial order of set inclusion (⊆) among the subsets of a three-element set

49: 3176:

Evans, T.S.; Calmon, L.; Vasiliauskaite, V. (2020), "The Longest Path in the Price Model",

2952:, Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, pp. 845–854, 2370: 2269: 2366: 2265: 1955: 1706:, Cambridge Computer Science Texts, vol. 14, Cambridge University Press, p. 27, 1490: 1474: 1101: 1095: 769: 743: 293:. Both of these DAGs produce the same partial order, in which the vertices are ordered as 3199: 3064: 2984: 2023: 1768: 3332: 3319:

Lee, C. Y. (1959), "Representation of switching circuits by binary-decision programs",

3216: 2873: 2123: 1926: 1580: 1514: 1503: 1482: 1461: 1437: 731: 116: 61: 2950:

Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01)

1660:, Springer Monographs in Mathematics (2nd ed.), Springer-Verlag, pp. 32–34, 1448:. The final triangle reached in this path must be the Delaunay triangle that contains 1161:

Directed acyclic graph representations of partial orderings have many applications in

17: 3453: 3008: 2666: 2237: 2223: 2037: 1604: 1414: 1372: 1125: 432: 428: 372: 195: 3430: 3408: 3367: 3275: 3162: 2930: 2703:

Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks

2450: 2069: 1825:, Algorithms and Computation in Mathematics, vol. 5, Springer, pp. 92–93, 1212:

A somewhat different DAG-based formulation of scheduling constraints is used by the

994:

to find. An arbitrary directed graph may also be transformed into a DAG, called its

448: 3117: 3012: 2728: 2670: 2292: 1991: 1979: 1918: 1907: 1727: 1344: 793: 493: 191: 132: 45: 2945: 2204: 2040:; Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", 1363: 1204: 962: 474:

Adding the red edges to the blue directed acyclic graph produces another DAG, the

468: 3242:, Lecture Notes in Computer Science, vol. 1264, Springer, pp. 116–129, 3072: 2849:

Kirkpatrick, Bonnie B. (April 2011), "Haplotypes versus genotypes on pedigrees",

1311:. An example of this type of directed acyclic graph are those encountered in the 3289: 2976:

Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems

2944:

Bender, Michael A.; Pemmasani, Giridhar; Skiena, Steven; Sumazin, Pavel (2001),

2912: 2084: 1987: 1396: 1392: 1383: 1332: 1312: 1308: 1260: 1189: 1174: 1170: 1166: 1079: 921: 897: 739: 65: 41: 3207: 1045:

to test reachability from each vertex. Alternatively, it can be solved in time

2835: 2588: 2119: 1246: 735: 713:{\displaystyle a_{n}=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}2^{k(n-k)}a_{n-k}.} 3257: 2277: 3435: 3359: 3154: 3018:

Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures

2819: 2362: 1960: 1882:, Dover Books on Computer Science, Courier Dover Publications, p. 142, 1575:

it would take to list out all of the sequences separately. For example, the

1486: 1417: 1323: 1007: 901: 828: 800: 3225: 3109: 3080: 2882: 2863: 2579:

Dennis, Jack B. (1974), "First version of a data flow procedure language",

1326:

between the events, we will have a directed acyclic graph. For instance, a

2432: 2050: 1594:

The same idea of using a DAG to represent a family of paths occurs in the

1440:

queries to be answered efficiently: to find the location of a query point

870:

the edges of an undirected tree away from a particular vertex, called the

523:

The family of topological orderings of a DAG is the same as the family of

2250:. Series of Books in the Mathematical Sciences (1st ed.). New York: 1626:

Thulasiraman, K.; Swamy, M. N. S. (1992), "5.7 Acyclic Directed Graphs",

1271: 1194: 1162: 932:. Different total orders may lead to the same acyclic orientation, so an 912:

successfully orders all the vertices without meeting an error condition.

849: 816: 3390: 409:

of the DAG. It is a subgraph of the DAG, formed by discarding the edges

177: 2528:

What Every Engineer Should Know About Decision Making Under Uncertainty

2501:

The Compiler Design Handbook: Optimizations and Machine Code Generation

2042:

Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)

1145: 991: 2247:

Computers and Intractability: A Guide to the Theory of NP-Completeness

857:) is a multitree formed by orienting the edges of an undirected tree. 2583:, Lecture Notes in Computer Science, vol. 19, pp. 362–376, 2014: 943:

acyclic orientations. The number of acyclic orientations is equal to

119:, each edge has an orientation, from one vertex to another vertex. A 809: 3190: 2297:

Structural Models: An Introduction to the Theory of Directed Graphs

2087:(1987), "The recovery of causal poly-trees from statistical data", 156:

Reachability relation, transitive closure, and transitive reduction

3145: 1469:

who went on to produce the first model of a citation network, the

1362: 1203: 961: 165: 32: 31: 1760:

Loop Transformations for Restructuring Compilers: The Foundations

1906:

Robinson, R. W. (1973), "Counting labeled acyclic digraphs", in

1798:, Springer Monographs in Mathematics, Springer, pp. 36–39, 1588: 1494: 1316: 780:

preserves the property that all matrix coefficients are 0 or 1.

201:

on the vertices of the DAG. In this partial order, two vertices

263:

has the same reachability relation as the DAG with three edges

2706:, Society for Industrial and Applied Mathematics, p. 58, 2642:

Large-Scale Software Architecture: A Practical Guide using UML

1603:

binary decision diagrams can be viewed as compressed forms of

1407: 1250: 1849:; Wayne, Kevin (2011), "4,2,25 Unique topological ordering", 776:, its adjacency matrix must have a zero diagonal, so adding 419:

for which the DAG also contains a longer directed path from

2946:"Finding least common ancestors in directed acyclic graphs" 819:, a DAG formed by orienting the edges of an undirected tree 560: 539:

problem of counting directed acyclic graphs was studied by

3443: 3383:

Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)

2905:

IEEE Symposium on Information Visualization (INFOVIS 2005)

920:

Any undirected graph may be made into a DAG by choosing a

1278:

efficiently. At a higher level of code organization, the

982:

Any directed graph may be made into a DAG by removing a

3097:

Journal of the American Society for Information Science

1736:, Monographs in Computer Science, Springer, p. 9, 1132:

from a given starting vertex in DAGs in linear time by

764:

is a (0,1) matrix with all eigenvalues positive, where

727: 3346:

Akers, Sheldon B. (1978), "Binary decision diagrams",

124:

acyclic graph is a directed graph that has no cycles.

1536: 584: 87:

Directed acyclic graphs are sometimes instead called

1996:"Acyclic digraphs and eigenvalues of (0,1)-matrices" 1656:

Bang-Jensen, Jørgen (2008), "2.1 Acyclic Digraphs",

356:

is automatically a transitively closed DAG, and has

1241:For instance, in electronic circuit design, static 348:, the graph that has a vertex for every element of 2898:"Interactive visualization of genealogical graphs" 1855:(4th ed.), Addison-Wesley, pp. 598–599, 1554: 1245:blocks can be represented as an acyclic system of 712: 660: 647: 2334: 2295:; Norman, Robert Z.; Cartwright, Dorwin (1965), 1703:Simulation Techniques for Discrete Event Systems 1169:after one of the cells has been changed, or the 2700:Shmulevich, Ilya; Dougherty, Edward R. (2010), 2425:23rd Australian Software Engineering Conference 219:exactly when there exists a directed path from 1570:Directed acyclic graphs may also be used as a 1315:though in this case the graphs considered are 1134:processing the vertices in a topological order 978:of the blue graph into a single yellow vertex. 558:1, 1, 3, 25, 543, 29281, 3781503, … (sequence 1795:Digraphs: Theory, Algorithms and Applications 1658:Digraphs: Theory, Algorithms and Applications 1201:for low-level computer program optimization. 1067:; this is a theoretical improvement over the 1065:exponent for matrix multiplication algorithms 478:of the blue graph. For each red or blue edge 8: 3385:, New York, NY, USA: ACM, pp. 348–356, 2143:Section 22.4, Topological sort, pp. 549–552. 1395:descent (mother-daughter relationships) and 1259:languages describe systems of operations on 1144:, and longest paths in arbitrary graphs are 1018:The transitive closure of a given DAG, with 1010:, and its condensation is the graph itself. 970:of the blue directed graph. It is formed by 2504:(2nd ed.), CRC Press, pp. 19–39, 2132:(2nd ed.), MIT Press and McGraw-Hill, 1513:is too simple to be a realistic model of a 1014:Transitive closure and transitive reduction 3042:Price, Derek J. de Solla (July 30, 1965), 2896:McGuffin, M. J.; Balakrishnan, R. (2005), 2462: 2460: 2155: 1173:of a piece of computer software after its 352:and an edge for every pair of elements in 3247: 3215: 3189: 3144: 2872: 2862: 2741:Probabilistic Networks and Expert Systems 2612:Touati, Sid; de Dinechin, Benoit (2014), 2477:(2nd ed.), CRC Press, p. 1181, 2282:, Problems GT7 and GT8, pp. 191–192. 2049: 2013: 1757:Banerjee, Utpal (1993), "Exercise 2(c)", 1535: 1352: 966:The yellow directed acyclic graph is the 695: 670: 659: 646: 644: 632: 613: 602: 589: 583: 2820:"Causal diagrams for empirical research" 2639:Garland, Jeff; Anthony, Richard (2003), 730:proved, that the same numbers count the 540: 366: 139:when there exists a path that starts at 2498:Srikant, Y. N.; Shankar, Priti (2007), 2106: 2104: 1901: 1899: 1615: 1214:program evaluation and review technique 500:: there exists a blue path starting at 2794:Encyclopedia of Epidemiology, Volume 1 2679:, Oxford University Press, p. 4, 2645:, John Wiley & Sons, p. 215, 2618:, John Wiley & Sons, p. 123, 2410: 2322: 2310: 2151: 2149: 1912:New Directions in the Theory of Graphs 1879:A Short Course in Discrete Mathematics 1651: 1649: 1647: 1621: 1619: 1313:causal set approach to quantum gravity 27:Directed graph with no directed cycles 1733:The Design and Analysis of Algorithms 1686:Graph theory: an algorithmic approach 1177:has been changed. In this context, a 572:These numbers may be computed by the 7: 2299:, John Wiley & Sons, p. 63 1630:, John Wiley and Son, p. 118, 883:Topological sorting and recognition 458:of a directed acyclic graph: every 36:Example of a directed acyclic graph 3446:– an online tool for creating DAGs 3333:10.1002/j.1538-7305.1959.tb01585.x 2767:The Technology Management Handbook 1914:, Academic Press, pp. 239–273 1688:, Academic Press, pp. 170–174 1026:edges, may be constructed in time 936:-vertex graph can have fewer than 651: 131:of a directed graph is said to be 25: 2467:Gross, Jonathan L.; Yellen, Jay; 1188:For instance, when one cell of a 2851:Algorithms for Molecular Biology 2205:"Acyclic orientations of graphs" 1276:common subexpression elimination 808: 792: 467: 447: 194:of a DAG can be formalized as a 176: 164: 3044:"Networks of Scientific Papers" 1822:Graphs, Networks and Algorithms 916:Construction from cyclic graphs 332:) in the reachability relation 3348:IEEE Transactions on Computers 3295:Applied Combinatorics on Words 3240:Combinatorial Pattern Matching 2770:, CRC Press, p. 9-7, 2739:(1999), "3.2.1 Moralization", 2335:Bang-Jensen & Gutin (2008) 2179:, Springer, pp. 179–181, 1549: 1543: 1371:, with many marriages between 1280:acyclic dependencies principle 686: 674: 629: 619: 1: 3321:Bell System Technical Journal 2615:Advanced Backend Optimization 1628:Graphs: Theory and Algorithms 1359:Genealogy and version history 1004:strongly connected components 405:of the reachability relation 3073:10.1126/science.149.3683.510 2743:, Springer, pp. 31–33, 2224:10.1016/0012-365X(73)90108-8 2001:Journal of Integer Sequences 1424:, the algorithm maintains a 1404:distributed revision control 1197:for program compilation and 976:strongly connected component 772:. Because a DAG cannot have 393:for every pair of vertices ( 324:for every pair of vertices ( 3133:Journal of Complex Networks 2913:10.1109/INFVIS.2005.1532124 2552:Sapatnekar, Sachin (2004), 2401:Cormen et al. 2001, p. 966. 2176:The Algorithm Design Manual 1921:; Palmer, Edgar M. (1973), 1819:Jungnickel, Dieter (2012), 1577:directed acyclic word graph 1286:Feedforward neural networks 1225:in this DAG represents the 1108:, such that no edges leave 3481: 3208:10.1038/s41598-020-67421-8 2531:, CRC Press, p. 160, 2173:Skiena, Steven S. (2009), 2129:Introduction to Algorithms 1295: 1093: 928:of the edges is called an 886: 834:strongly unambiguous graph 784:Related families of graphs 552: = 0, 1, 2, 3, … 227:in the DAG; that is, when 68:. That is, it consists of 2764:Dorf, Richard C. (1998), 2589:10.1007/3-540-06859-7_145 2558:, Springer, p. 133, 2252:W. H. Freeman and Company 1402:The version history of a 1221:to perform the task. The 531:Combinatorial enumeration 3258:10.1007/3-540-63220-4_55 2979:, Springer, p. 59, 2791:Boslaugh, Sarah (2008), 2474:Handbook of Graph Theory 2427:, IEEE, pp. 48–57, 1956:"Weisstein's Conjecture" 1763:, Springer, p. 19, 1233:Data processing networks 866:is a polytree formed by 754:of a DAG if and only if 543:. The number of DAGs on 183:Its transitive reduction 3465:Directed acyclic graphs 3360:10.1109/TC.1978.1675141 2836:10.1093/biomet/82.4.669 2737:Spiegelhalter, David J. 2363:10.1287/mnsc.22.11.1268 1596:binary decision diagram 1467:Derek J. de Solla Price 1387:father's side) causing 151:Mathematical properties 89:acyclic directed graphs 3110:10.1002/asi.4630270505 2973:Bartlang, Udo (2010), 2864:10.1186/1748-7188-6-10 2525:Wang, John X. (2002), 1572:compact representation 1556: 1555:{\displaystyle \ln(n)} 1434:Delaunay triangulation 1430:randomized incremental 1422:computational geometry 1380: 1209: 1199:instruction scheduling 1142:Bellman–Ford algorithm 979: 878:Computational problems 714: 618: 547:labeled vertices, for 376: 54:directed acyclic graph 37: 18:Directed Acyclic Graph 3155:10.1093/comnet/cnu039 2818:Pearl, Judea (1995), 2797:, SAGE, p. 255, 2733:Lauritzen, Steffen L. 2581:Programming Symposium 2433:10.1109/ASWEC.2014.15 2116:Leiserson, Charles E. 2051:10.1145/191666.191778 1923:Graphical Enumeration 1557: 1523:Barabási–Albert model 1366: 1317:transitively complete 1288:are another example. 1207: 1061: < 2.373 965: 874:of the arborescence. 715: 598: 370: 192:reachability relation 82:topologically ordered 35: 2212:Discrete Mathematics 2044:, pp. 330–336, 1700:Mitrani, I. (1982), 1534: 1495:transitive reduction 1353:topological ordering 1257:Dataflow programming 1138:Dijkstra's algorithm 1114:maximum flow problem 1039:breadth-first search 959:of the given graph. 957:chromatic polynomial 582: 517:topological ordering 456:topological ordering 439:Topological ordering 381:transitive reduction 135:from another vertex 3391:10.1145/37888.37941 3200:2020NatSR..1010503E 3065:1965Sci...149..510D 2985:2010aamf.book.....B 2727:Cowell, Robert G.; 2201:Stanley, Richard P. 2024:2004JIntS...7...33M 1769:1993ltfr.book.....B 1682:Christofides, Nicos 1473:. In this case the 1367:Family tree of the 1243:combinational logic 1183:circular dependency 984:feedback vertex set 930:acyclic orientation 894:Topological sorting 889:Topological sorting 728:McKay et al. (2004) 574:recurrence relation 3427:Weisstein, Eric W. 3178:Scientific Reports 2907:, pp. 16–23, 2350:Management Science 2169:depth-first search 2096:, pp. 222–228 1982:; Wanless, I. M.; 1952:Weisstein, Eric W. 1552: 1500:main path analysis 1381: 1265:parallel algorithm 1210: 1043:depth-first search 980: 906:depth-first search 710: 476:transitive closure 377: 312:transitive closure 239:is reachable from 38: 3431:"Acyclic Digraph" 3400:978-0-8186-0781-3 3267:978-3-540-63220-7 3059:(3683): 510–515, 3028:978-0-8218-7533-9 2994:978-3-8348-9645-2 2959:978-0-89871-490-6 2922:978-0-7803-9464-3 2804:978-1-4129-2816-8 2777:978-0-8493-8577-3 2750:978-0-387-98767-5 2713:978-0-89871-692-4 2686:978-0-19-803928-0 2625:978-1-118-64894-0 2598:978-3-540-06859-4 2565:978-1-4020-7671-8 2538:978-0-8247-4373-4 2511:978-1-4200-4383-9 2484:978-1-4398-8018-0 2442:978-1-4799-3149-1 2357:(11): 1268–1272, 2242:Johnson, David S. 2238:Garey, Michael R. 2186:978-1-84800-070-4 2156:Jungnickel (2012) 2120:Rivest, Ronald L. 2112:Cormen, Thomas H. 2038:Furnas, George W. 2027:, Article 04.3.3. 1936:978-0-12-324245-7 1889:978-0-486-43946-4 1862:978-0-13-276256-4 1847:Sedgewick, Robert 1832:978-3-642-32278-5 1805:978-1-84800-998-1 1778:978-0-7923-9318-4 1743:978-0-387-97687-7 1667:978-1-84800-997-4 1637:978-0-471-51356-8 1525:. However, since 1479:citation analysis 1389:pedigree collapse 1377:pedigree collapse 1369:Ptolemaic dynasty 1341:influence diagram 1292:Causal structures 908:graph traversal. 726:conjectured, and 724:Eric W. Weisstein 658: 537:graph enumeration 525:linear extensions 403:covering relation 16:(Redirected from 3472: 3440: 3439: 3413: 3411: 3378: 3372: 3370: 3343: 3337: 3335: 3316: 3310: 3308: 3286: 3280: 3278: 3251: 3235: 3229: 3228: 3219: 3193: 3173: 3167: 3165: 3148: 3128: 3122: 3120: 3091: 3085: 3083: 3048: 3039: 3033: 3031: 3005: 2999: 2997: 2970: 2964: 2962: 2941: 2935: 2933: 2902: 2893: 2887: 2885: 2876: 2866: 2846: 2840: 2838: 2815: 2809: 2807: 2788: 2782: 2780: 2761: 2755: 2753: 2729:Dawid, A. Philip 2724: 2718: 2716: 2697: 2691: 2689: 2663: 2657: 2655: 2636: 2630: 2628: 2609: 2603: 2601: 2576: 2570: 2568: 2549: 2543: 2541: 2522: 2516: 2514: 2495: 2489: 2487: 2464: 2455: 2453: 2420: 2414: 2408: 2402: 2399: 2393: 2390: 2384: 2381: 2375: 2373: 2344: 2338: 2332: 2326: 2320: 2314: 2308: 2302: 2300: 2289: 2283: 2281: 2234: 2228: 2226: 2209: 2197: 2191: 2189: 2165: 2159: 2153: 2144: 2142: 2108: 2099: 2097: 2095: 2083:Rebane, George; 2080: 2074: 2072: 2053: 2034: 2028: 2026: 2017: 1988:Sloane, N. J. A. 1972: 1966: 1965: 1964: 1947: 1941: 1939: 1915: 1903: 1894: 1892: 1873: 1867: 1865: 1843: 1837: 1835: 1816: 1810: 1808: 1789: 1783: 1781: 1754: 1748: 1746: 1724: 1718: 1716: 1697: 1691: 1689: 1678: 1672: 1670: 1653: 1642: 1640: 1623: 1600:truth assignment 1566:Data compression 1561: 1559: 1558: 1553: 1515:citation network 1491:network analysis 1483:Court judgements 1451: 1447: 1443: 1406:system, such as 1391:. The graphs of 1328:Bayesian network 1324:causal relations 1298:Bayesian network 1179:dependency graph 1077: 1062: 1055: 1037:by using either 1036: 1025: 1021: 988:feedback arc set 954: 950: 942: 935: 812: 796: 779: 767: 763: 752:adjacency matrix 749: 719: 717: 716: 711: 706: 705: 690: 689: 665: 664: 663: 650: 643: 642: 617: 612: 594: 593: 563: 553: 546: 507: 503: 499: 491: 487: 471: 451: 426: 422: 418: 408: 400: 396: 392: 363: 355: 351: 347: 339: 335: 331: 327: 323: 306: 292: 282: 272: 262: 252: 242: 238: 234: 230: 226: 222: 218: 208: 204: 200: 180: 168: 146: 142: 138: 130: 93:acyclic digraphs 50:computer science 21: 3480: 3479: 3475: 3474: 3473: 3471: 3470: 3469: 3460:Directed graphs 3450: 3449: 3425: 3424: 3421: 3416: 3401: 3380: 3379: 3375: 3345: 3344: 3340: 3318: 3317: 3313: 3306: 3288: 3287: 3283: 3268: 3237: 3236: 3232: 3175: 3174: 3170: 3130: 3129: 3125: 3093: 3092: 3088: 3046: 3041: 3040: 3036: 3029: 3007: 3006: 3002: 2995: 2972: 2971: 2967: 2960: 2943: 2942: 2938: 2923: 2900: 2895: 2894: 2890: 2848: 2847: 2843: 2817: 2816: 2812: 2805: 2790: 2789: 2785: 2778: 2763: 2762: 2758: 2751: 2726: 2725: 2721: 2714: 2699: 2698: 2694: 2687: 2676:Causal Learning 2665: 2664: 2660: 2653: 2638: 2637: 2633: 2626: 2611: 2610: 2606: 2599: 2578: 2577: 2573: 2566: 2551: 2550: 2546: 2539: 2524: 2523: 2519: 2512: 2497: 2496: 2492: 2485: 2466: 2465: 2458: 2443: 2422: 2421: 2417: 2409: 2405: 2400: 2396: 2391: 2387: 2382: 2378: 2346: 2345: 2341: 2333: 2329: 2321: 2317: 2309: 2305: 2291: 2290: 2286: 2262: 2236: 2235: 2231: 2207: 2199: 2198: 2194: 2187: 2172: 2166: 2162: 2154: 2147: 2140: 2124:Stein, Clifford 2110: 2109: 2102: 2093: 2082: 2081: 2077: 2062: 2036: 2035: 2031: 1974: 1973: 1969: 1950: 1949: 1948: 1944: 1937: 1917: 1905: 1904: 1897: 1890: 1875: 1874: 1870: 1863: 1845: 1844: 1840: 1833: 1818: 1817: 1813: 1806: 1791: 1790: 1786: 1779: 1756: 1755: 1751: 1744: 1726: 1725: 1721: 1714: 1699: 1698: 1694: 1680: 1679: 1675: 1668: 1655: 1654: 1645: 1638: 1625: 1624: 1617: 1613: 1568: 1532: 1531: 1493:. For instance 1458: 1456:Citation graphs 1449: 1445: 1441: 1373:close relatives 1361: 1300: 1294: 1235: 1159: 1154: 1122: 1120:Path algorithms 1102:closure problem 1098: 1096:Closure problem 1092: 1090:Closure problem 1068: 1057: 1046: 1027: 1023: 1019: 1016: 952: 944: 937: 933: 918: 904:numbering of a 891: 885: 880: 853:(also called a 842:undirected tree 832:(also called a 824: 823: 822: 821: 820: 813: 805: 804: 797: 786: 777: 770:identity matrix 765: 755: 747: 742:. The proof is 691: 666: 645: 628: 585: 580: 579: 559: 548: 544: 541:Robinson (1973) 533: 513: 512: 511: 510: 509: 505: 501: 497: 489: 479: 472: 464: 463: 452: 441: 424: 420: 410: 406: 398: 394: 384: 357: 353: 349: 341: 337: 333: 329: 325: 315: 294: 284: 274: 264: 254: 244: 240: 236: 232: 228: 224: 220: 210: 209:are ordered as 206: 202: 198: 188: 187: 186: 185: 184: 181: 173: 172: 169: 158: 153: 144: 140: 136: 128: 101: 66:directed cycles 44:, particularly 28: 23: 22: 15: 12: 11: 5: 3478: 3476: 3468: 3467: 3462: 3452: 3451: 3448: 3447: 3441: 3420: 3419:External links 3417: 3415: 3414: 3399: 3373: 3354:(6): 509–516, 3338: 3327:(4): 985–999, 3311: 3304: 3281: 3266: 3249:10.1.1.53.6273 3230: 3168: 3139:(2): 189–203, 3123: 3104:(5): 292–306, 3086: 3034: 3027: 3000: 2993: 2965: 2958: 2936: 2921: 2888: 2841: 2830:(4): 669–709, 2810: 2803: 2783: 2776: 2756: 2749: 2719: 2712: 2692: 2685: 2667:Gopnik, Alison 2658: 2651: 2631: 2624: 2604: 2597: 2571: 2564: 2544: 2537: 2517: 2510: 2490: 2483: 2456: 2441: 2415: 2403: 2394: 2385: 2376: 2339: 2327: 2315: 2303: 2284: 2260: 2229: 2218:(2): 171–178, 2192: 2185: 2160: 2145: 2138: 2100: 2075: 2061:978-0897916509 2060: 2029: 1967: 1942: 1935: 1929:, p. 19, 1927:Academic Press 1895: 1888: 1868: 1861: 1838: 1831: 1811: 1804: 1784: 1777: 1749: 1742: 1719: 1712: 1692: 1673: 1666: 1643: 1636: 1614: 1612: 1609: 1605:decision trees 1581:data structure 1567: 1564: 1551: 1548: 1545: 1542: 1539: 1504:citation graph 1475:citation count 1462:citation graph 1457: 1454: 1438:point location 1432:algorithm for 1360: 1357: 1296:Main article: 1293: 1290: 1234: 1231: 1158: 1155: 1153: 1150: 1126:shortest paths 1121: 1118: 1094:Main article: 1091: 1088: 1015: 1012: 917: 914: 887:Main article: 884: 881: 879: 876: 814: 807: 806: 798: 791: 790: 789: 788: 787: 785: 782: 734:for which all 732:(0,1) matrices 721: 720: 709: 704: 701: 698: 694: 688: 685: 682: 679: 676: 673: 669: 662: 657: 654: 649: 641: 638: 635: 631: 627: 624: 621: 616: 611: 608: 605: 601: 597: 592: 588: 570: 569: 532: 529: 504:and ending at 473: 466: 465: 453: 446: 445: 444: 443: 442: 440: 437: 429:graph drawings 182: 175: 174: 170: 163: 162: 161: 160: 159: 157: 154: 152: 149: 117:directed graph 100: 97: 62:directed graph 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 3477: 3466: 3463: 3461: 3458: 3457: 3455: 3445: 3442: 3438: 3437: 3432: 3428: 3423: 3422: 3418: 3410: 3406: 3402: 3396: 3392: 3388: 3384: 3377: 3374: 3369: 3365: 3361: 3357: 3353: 3349: 3342: 3339: 3334: 3330: 3326: 3322: 3315: 3312: 3307: 3305:9780521848022 3301: 3297: 3296: 3291: 3285: 3282: 3277: 3273: 3269: 3263: 3259: 3255: 3250: 3245: 3241: 3234: 3231: 3227: 3223: 3218: 3213: 3209: 3205: 3201: 3197: 3192: 3187: 3183: 3179: 3172: 3169: 3164: 3160: 3156: 3152: 3147: 3142: 3138: 3134: 3127: 3124: 3119: 3115: 3111: 3107: 3103: 3099: 3098: 3090: 3087: 3082: 3078: 3074: 3070: 3066: 3062: 3058: 3054: 3053: 3045: 3038: 3035: 3030: 3024: 3020: 3019: 3014: 3013:Sharir, Micha 3010: 3004: 3001: 2996: 2990: 2986: 2982: 2978: 2977: 2969: 2966: 2961: 2955: 2951: 2947: 2940: 2937: 2932: 2928: 2924: 2918: 2914: 2910: 2906: 2899: 2892: 2889: 2884: 2880: 2875: 2870: 2865: 2860: 2856: 2852: 2845: 2842: 2837: 2833: 2829: 2825: 2821: 2814: 2811: 2806: 2800: 2796: 2795: 2787: 2784: 2779: 2773: 2769: 2768: 2760: 2757: 2752: 2746: 2742: 2738: 2734: 2730: 2723: 2720: 2715: 2709: 2705: 2704: 2696: 2693: 2688: 2682: 2678: 2677: 2672: 2671:Schulz, Laura 2668: 2662: 2659: 2654: 2652:9780470856383 2648: 2644: 2643: 2635: 2632: 2627: 2621: 2617: 2616: 2608: 2605: 2600: 2594: 2590: 2586: 2582: 2575: 2572: 2567: 2561: 2557: 2556: 2548: 2545: 2540: 2534: 2530: 2529: 2521: 2518: 2513: 2507: 2503: 2502: 2494: 2491: 2486: 2480: 2476: 2475: 2470: 2463: 2461: 2457: 2452: 2448: 2444: 2438: 2434: 2430: 2426: 2419: 2416: 2412: 2411:Skiena (2009) 2407: 2404: 2398: 2395: 2389: 2386: 2380: 2377: 2372: 2368: 2364: 2360: 2356: 2352: 2351: 2343: 2340: 2336: 2331: 2328: 2324: 2323:Skiena (2009) 2319: 2316: 2312: 2311:Skiena (2009) 2307: 2304: 2298: 2294: 2293:Harary, Frank 2288: 2285: 2279: 2275: 2271: 2267: 2263: 2261:9780716710455 2257: 2253: 2249: 2248: 2243: 2239: 2233: 2230: 2225: 2221: 2217: 2213: 2206: 2202: 2196: 2193: 2188: 2182: 2178: 2177: 2170: 2164: 2161: 2157: 2152: 2150: 2146: 2141: 2139:0-262-03293-7 2135: 2131: 2130: 2125: 2121: 2117: 2113: 2107: 2105: 2101: 2092: 2091: 2086: 2079: 2076: 2071: 2067: 2063: 2057: 2052: 2047: 2043: 2039: 2033: 2030: 2025: 2021: 2016: 2011: 2007: 2003: 2002: 1997: 1993: 1989: 1985: 1984:Oggier, F. E. 1981: 1977: 1971: 1968: 1963: 1962: 1957: 1953: 1946: 1943: 1938: 1932: 1928: 1924: 1920: 1919:Harary, Frank 1913: 1909: 1902: 1900: 1896: 1891: 1885: 1881: 1880: 1872: 1869: 1864: 1858: 1854: 1853: 1848: 1842: 1839: 1834: 1828: 1824: 1823: 1815: 1812: 1807: 1801: 1797: 1796: 1788: 1785: 1780: 1774: 1770: 1766: 1762: 1761: 1753: 1750: 1745: 1739: 1735: 1734: 1729: 1728:Kozen, Dexter 1723: 1720: 1715: 1713:9780521282826 1709: 1705: 1704: 1696: 1693: 1687: 1683: 1677: 1674: 1669: 1663: 1659: 1652: 1650: 1648: 1644: 1639: 1633: 1629: 1622: 1620: 1616: 1610: 1608: 1606: 1601: 1597: 1592: 1590: 1586: 1582: 1578: 1573: 1565: 1563: 1546: 1540: 1537: 1528: 1527:Price's model 1524: 1520: 1516: 1512: 1507: 1505: 1501: 1496: 1492: 1488: 1484: 1480: 1476: 1472: 1468: 1463: 1455: 1453: 1439: 1435: 1431: 1427: 1423: 1419: 1416: 1411: 1409: 1405: 1400: 1398: 1394: 1390: 1385: 1378: 1374: 1370: 1365: 1358: 1356: 1354: 1348: 1346: 1342: 1338: 1334: 1329: 1325: 1320: 1318: 1314: 1310: 1306: 1299: 1291: 1289: 1287: 1283: 1281: 1277: 1273: 1268: 1266: 1262: 1258: 1254: 1252: 1248: 1244: 1239: 1232: 1230: 1228: 1227:critical path 1224: 1219: 1215: 1206: 1202: 1200: 1196: 1191: 1186: 1184: 1180: 1176: 1172: 1168: 1164: 1156: 1151: 1149: 1147: 1143: 1139: 1135: 1131: 1130:longest paths 1127: 1119: 1117: 1115: 1111: 1107: 1103: 1097: 1089: 1087: 1083: 1081: 1075: 1071: 1066: 1060: 1053: 1049: 1044: 1040: 1034: 1030: 1022:vertices and 1013: 1011: 1009: 1005: 1001: 997: 993: 989: 985: 977: 973: 969: 964: 960: 958: 948: 940: 931: 927: 923: 915: 913: 909: 907: 903: 899: 895: 890: 882: 877: 875: 873: 869: 865: 864: 858: 856: 855:directed tree 852: 851: 845: 843: 839: 835: 831: 830: 818: 811: 802: 795: 783: 781: 775: 771: 762: 759: + 758: 753: 745: 741: 738:are positive 737: 733: 729: 725: 707: 702: 699: 696: 692: 683: 680: 677: 671: 667: 655: 652: 639: 636: 633: 625: 622: 614: 609: 606: 603: 599: 595: 590: 586: 578: 577: 576: 575: 567: 562: 557: 556: 555: 551: 542: 538: 530: 528: 526: 521: 518: 495: 486: 482: 477: 470: 461: 457: 450: 438: 436: 434: 433:Hasse diagram 430: 417: 413: 404: 391: 387: 382: 374: 373:Hasse diagram 369: 365: 361: 345: 322: 318: 313: 308: 305: 301: 297: 291: 287: 281: 277: 271: 267: 261: 257: 251: 247: 217: 213: 197: 196:partial order 193: 179: 167: 155: 150: 148: 134: 125: 122: 118: 114: 110: 107:is formed by 106: 98: 96: 94: 90: 85: 83: 79: 76:(also called 75: 71: 67: 63: 59: 55: 51: 47: 43: 34: 30: 19: 3434: 3382: 3376: 3351: 3347: 3341: 3324: 3320: 3314: 3294: 3290:Lothaire, M. 3284: 3239: 3233: 3184:(1): 10503, 3181: 3177: 3171: 3136: 3132: 3126: 3101: 3095: 3089: 3056: 3050: 3037: 3017: 3003: 2975: 2968: 2949: 2939: 2904: 2891: 2854: 2850: 2844: 2827: 2823: 2813: 2793: 2786: 2766: 2759: 2740: 2722: 2702: 2695: 2675: 2661: 2641: 2634: 2614: 2607: 2580: 2574: 2554: 2547: 2527: 2520: 2500: 2493: 2473: 2424: 2418: 2406: 2397: 2388: 2379: 2354: 2348: 2342: 2330: 2318: 2306: 2296: 2287: 2245: 2232: 2215: 2211: 2195: 2175: 2163: 2158:, pp. 50–51. 2128: 2089: 2085:Pearl, Judea 2078: 2041: 2032: 2015:math/0310423 2005: 1999: 1980:Royle, G. F. 1976:McKay, B. D. 1970: 1959: 1945: 1922: 1911: 1878: 1871: 1851: 1841: 1821: 1814: 1794: 1787: 1759: 1752: 1732: 1722: 1702: 1695: 1685: 1676: 1657: 1627: 1593: 1569: 1508: 1459: 1425: 1412: 1401: 1384:Family trees 1382: 1349: 1345:epidemiology 1336: 1321: 1309:causal loops 1301: 1284: 1269: 1261:data streams 1255: 1240: 1236: 1223:longest path 1211: 1187: 1171:object files 1160: 1152:Applications 1123: 1109: 1105: 1099: 1084: 1080:dense graphs 1073: 1069: 1058: 1051: 1047: 1032: 1028: 1017: 1002:each of its 996:condensation 981: 968:condensation 946: 938: 919: 910: 892: 871: 863:arborescence 861: 859: 854: 848: 846: 837: 833: 827: 825: 768:denotes the 760: 756: 740:real numbers 722: 571: 549: 534: 522: 514: 484: 480: 415: 411: 389: 385: 378: 359: 343: 320: 316: 309: 303: 299: 295: 289: 285: 279: 275: 269: 265: 259: 255: 249: 245: 215: 211: 189: 143:and ends at 126: 102: 92: 88: 86: 77: 57: 53: 46:graph theory 39: 29: 3009:Pach, János 2469:Zhang, Ping 1916:. See also 1519:Price model 1511:Price model 1471:Price model 1465:Papers" by 1426:history DAG 1397:patrilineal 1393:matrilineal 1333:moral graph 1303:follow any 1247:logic gates 1190:spreadsheet 1175:source code 1167:spreadsheet 1000:contracting 972:contracting 926:orientation 922:total order 898:linear time 746:: a matrix 736:eigenvalues 99:Definitions 42:mathematics 3454:Categories 3191:1903.03667 2857:(10): 10, 2824:Biometrika 1908:Harary, F. 1852:Algorithms 1611:References 1418:algorithms 1415:randomized 1218:milestones 1163:scheduling 1157:Scheduling 1078:bound for 774:self-loops 231:can reach 3436:MathWorld 3244:CiteSeerX 3146:1310.8224 2413:, p. 469. 2325:, p. 496. 2313:, p. 495. 2278:247570676 2126:(2001) , 1961:MathWorld 1541:⁡ 1487:prior art 1272:compilers 1195:makefiles 1148:to find. 902:postorder 868:orienting 829:multitree 801:multitree 744:bijective 700:− 681:− 637:− 623:− 600:∑ 494:reachable 401:) in the 133:reachable 127:A vertex 3409:14796451 3368:21028055 3292:(2005), 3276:17045308 3226:32601403 3163:10228152 3081:14325149 2931:15449409 2883:21504603 2673:(2007), 2471:(2013), 2451:17570052 2337:, p. 38. 2244:(1979). 2203:(1973), 2070:18710118 1994:(2004), 1992:Wilf, H. 1730:(1992), 1684:(1975), 1413:In many 1375:causing 1337:marrying 951:, where 850:polytree 838:mangrove 817:polytree 109:vertices 70:vertices 64:with no 3444:DAGitty 3217:7324613 3196:Bibcode 3118:8536863 3061:Bibcode 3052:Science 2981:Bibcode 2874:3102622 2371:0403596 2270:0519066 2020:Bibcode 1910:(ed.), 1765:Bibcode 1585:strings 1146:NP-hard 1140:or the 1063:is the 992:NP-hard 955:is the 564:in the 561:A003024 111:and by 60:) is a 3407: 3397: 3366: 3302: 3274: 3264: 3246: 3224: 3214: 3161: 3116: 3079: 3025: 2991: 2956: 2929: 2919: 2881: 2871: 2801: 2774: 2747: 2710: 2683: 2649: 2622: 2595: 2562: 2555:Timing 2535: 2508: 2481: 2449: 2439: 2369: 2276: 2268: 2258: 2183: 2136: 2068: 2058: 2008:: 33, 1933: 1886: 1859: 1829: 1802: 1775: 1740: 1710: 1664: 1634: 1521:, the 1056:where 750:is an 283:, and 48:, and 3405:S2CID 3364:S2CID 3272:S2CID 3186:arXiv 3159:S2CID 3141:arXiv 3114:S2CID 3047:(PDF) 2927:S2CID 2901:(PDF) 2447:S2CID 2208:(PDF) 2094:(PDF) 2066:S2CID 2010:arXiv 1579:is a 1460:In a 1008:empty 998:, by 986:or a 974:each 949:(−1)| 836:or a 496:from 171:A DAG 113:edges 105:graph 74:edges 3395:ISBN 3352:C-27 3300:ISBN 3262:ISBN 3222:PMID 3077:PMID 3023:ISBN 2989:ISBN 2954:ISBN 2917:ISBN 2879:PMID 2799:ISBN 2772:ISBN 2745:ISBN 2708:ISBN 2681:ISBN 2647:ISBN 2620:ISBN 2593:ISBN 2560:ISBN 2533:ISBN 2506:ISBN 2479:ISBN 2437:ISBN 2274:OCLC 2256:ISBN 2181:ISBN 2167:For 2134:ISBN 2056:ISBN 1931:ISBN 1884:ISBN 1857:ISBN 1827:ISBN 1800:ISBN 1773:ISBN 1738:ISBN 1708:ISBN 1662:ISBN 1632:ISBN 1589:trie 1509:The 1305:path 1251:bits 1128:and 1100:The 872:root 566:OEIS 535:The 460:edge 431:. A 379:The 362:, ≤) 346:, ≤) 310:The 253:and 235:(or 205:and 190:The 121:path 78:arcs 72:and 52:, a 3387:doi 3356:doi 3329:doi 3254:doi 3212:PMC 3204:doi 3151:doi 3106:doi 3069:doi 3057:149 2909:doi 2869:PMC 2859:doi 2832:doi 2585:doi 2429:doi 2359:doi 2220:doi 2046:doi 1420:in 1408:Git 1270:In 1041:or 860:An 492:is 423:to 223:to 91:or 58:DAG 40:In 3456:: 3433:, 3429:, 3403:, 3393:, 3362:, 3350:, 3325:38 3323:, 3270:, 3260:, 3252:, 3220:, 3210:, 3202:, 3194:, 3182:10 3180:, 3157:, 3149:, 3135:, 3112:, 3102:27 3100:, 3075:, 3067:, 3055:, 3049:, 3015:, 3011:; 2987:, 2948:, 2925:, 2915:, 2903:, 2877:, 2867:, 2853:, 2828:82 2826:, 2822:, 2735:; 2731:; 2669:; 2591:, 2459:^ 2445:, 2435:, 2367:MR 2365:, 2355:22 2353:, 2272:. 2266:MR 2264:. 2254:. 2240:; 2214:, 2210:, 2148:^ 2122:; 2118:; 2114:; 2103:^ 2064:, 2054:, 2018:, 2004:, 1998:, 1990:; 1986:; 1978:; 1958:, 1954:, 1925:, 1898:^ 1771:, 1646:^ 1618:^ 1562:. 1538:ln 1506:. 1481:. 1452:. 1116:. 1082:. 1074:mn 1033:mn 847:A 844:. 826:A 815:A 799:A 568:). 515:A 488:, 483:→ 454:A 414:→ 397:, 388:→ 371:A 328:, 319:→ 307:. 302:≤ 298:≤ 288:→ 278:→ 273:, 268:→ 258:→ 248:→ 214:≤ 103:A 95:. 3412:. 3389:: 3371:. 3358:: 3336:. 3331:: 3309:. 3279:. 3256:: 3206:: 3198:: 3188:: 3166:. 3153:: 3143:: 3137:3 3121:. 3108:: 3084:. 3071:: 3063:: 3032:. 2998:. 2983:: 2963:. 2934:. 2911:: 2886:. 2861:: 2855:6 2839:. 2834:: 2808:. 2781:. 2754:. 2717:. 2690:. 2656:. 2629:. 2602:. 2587:: 2569:. 2542:. 2515:. 2488:. 2454:. 2431:: 2374:. 2361:: 2301:. 2280:. 2227:. 2222:: 2216:5 2190:. 2098:. 2073:. 2048:: 2022:: 2012:: 2006:7 1940:. 1893:. 1866:. 1836:. 1809:. 1782:. 1767:: 1747:. 1717:. 1690:. 1671:. 1641:. 1550:) 1547:n 1544:( 1450:q 1446:q 1442:q 1379:. 1110:C 1106:C 1076:) 1072:( 1070:O 1059:ω 1054:) 1052:n 1050:( 1048:O 1035:) 1031:( 1029:O 1024:m 1020:n 953:χ 947:χ 945:| 941:! 939:n 934:n 778:I 766:I 761:I 757:A 748:A 708:. 703:k 697:n 693:a 687:) 684:k 678:n 675:( 672:k 668:2 661:) 656:k 653:n 648:( 640:1 634:k 630:) 626:1 620:( 615:n 610:1 607:= 604:k 596:= 591:n 587:a 550:n 545:n 508:. 506:v 502:u 498:u 490:v 485:v 481:u 425:v 421:u 416:v 412:u 407:≤ 399:v 395:u 390:v 386:u 360:S 358:( 354:≤ 350:S 344:S 342:( 338:≤ 334:≤ 330:v 326:u 321:v 317:u 304:w 300:v 296:u 290:w 286:u 280:w 276:v 270:v 266:u 260:w 256:v 250:v 246:u 241:u 237:v 233:v 229:u 225:v 221:u 216:v 212:u 207:v 203:u 199:≤ 145:v 141:u 137:u 129:v 56:( 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index