Suppose we have a directed acyclic graph. The nodes are labeled with integers (which may be negative). Imagine that the labels represent payoffs or costs of taking an action associated with each node. In order to perform an action you must perform prerequisite actions indicated by the graph.(adsbygoogle = window.adsbygoogle || []).push({});

The question is whether there is a topological sort on this graph, such that at some point during the ordering, the sum of the labels on all the nodes up to that point becomes positive. This would represent a net profit from taking all actions up to that point.

Example:

[PLAIN]http://img535.imageshack.us/img535/5395/graph1f.png [Broken]

If we have the topological sort ABCED, the labels on ABCE sum to a positive number (1). So this graph does meet the criteria for being profitable - if you take actions A B C E in that order, you make a profit of 1. Note that if you also took action D, the sum would be -6, so you should stop after E. ABCED is a "profitable topological sort" because it has the prefix ABCE which is profitable. ABCDE is an example of a non-profitable topological sort.

The problem is to find an algorithm to determine whether a directed acyclic graph in general has a profitable topological sort.

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Directed acyclic graph profit sorting

Loading...

Similar Threads - Directed acyclic graph | Date |
---|---|

I Monty Hall - Multiple solutions via direct calculation? | Mar 8, 2016 |

Vacuous "If then" statements: Can you use direct proofs? | Dec 1, 2014 |

Maximum number of path for simple acyclic directed graph with start and end node | Jan 22, 2013 |

Hello, I am being asked to find the magnitude and directional sense | Sep 8, 2012 |

Direct proofs help | Jun 12, 2012 |

**Physics Forums - The Fusion of Science and Community**