1
$\begingroup$

Consider a DAG such as one shown below:

enter image description here

How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross through any node is minimized. Unique edges are edges that originate from unique nodes. So, if two edges are originating from the same node, they are counted only once.

Imagine the nodes represent people standing in a line. The edges represent a book representing the message from person 1 to person 2. Each person receives stack of books consisting of either books for themselves, or books to be passed to someone downstream. If a book is meant for themselves and nobody needs it downstream, they simply remove the book from the stack. If someone else also needs the book, they simply copy the book and keep passing along the book. How do I find an arrangement that minimizes the total stack of books that any one person has to ever handle? Because, you know, a person can only carry a certain weight of book, and it is best to minimize this maximum weight of book that needs to be handled by any person.

What if the books originating from different people had different weights?

Any thoughts, hints or just pointer to related concepts would be appreciated. Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you mean to say, you want to arrange the nodes in a sequence, such thar neighbors are placed as close as possible to each other? $\endgroup$
    – Russel
    Mar 5 at 1:21
  • $\begingroup$ I guess so, for a certain metric of "as close as possible". $\endgroup$
    – nepee
    Mar 5 at 1:49
  • $\begingroup$ Given a sequence of nodes from a DAG, define the "crossover" of a node with index i as the number of nodes j<i such that there exists an edge from j to an index i'>i. Is "find a sequence that minimizes the maximum crossover of a node" a way to rephrase your problem? $\endgroup$
    – Discrete lizard ♦
    Mar 6 at 11:44
  • $\begingroup$ @Discretelizard Yes, I think so, as long as the sequence is in topological order i.e. all edges are from node_j to node_i where i > j. $\endgroup$
    – nepee
    Mar 6 at 15:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.