1
$\begingroup$

Let's say that we have a ring topology $G$ and a set of $n$ nodes. The nodes are numbered from $0$ to $n-1$ clockwise. We have a set of paths $P$, where each path has clockwise direction. The first node of a path is called sender node and the last node of a path is called receiver node.

We have the below algorithm: At first, the algorithm orders the paths of $P$ as to the number of the sender node. The algorithm passes the paths on the above order and each path is colored by the smaller available color(two paths that share an edge must be colored with different color). The color ordering is arbitrary.

I want to show that the above algorithm colors any set of paths $P$ with load $L$(maximum number of paths going through any edge of the graph) using at most $2L$ colors.

Has anyone seen this problem before? Would you recommend any direction to search?

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.