My research has led me to a question on sums of integer labeled arc paths in an st-graph (single source single sink, acyclic, I actually have multi-graphs). The problem is to label all the arcs in a graph such that each path has a unique arc label sum from the set {0,..,p-1} with p being the number of paths from s to t. Here a path is a collection of arcs from s to t. There are some easy ways of doing this labeling that don't satisfy another restriction I have but I won't bother to explain that. I am trying to understand the seaming random ways to do this that brute force searching finds. Are there existing problems similar to this? Thanks.
Add a comment
|