Please consider a tree graph. There is one unique path connecting any two vertices.

However, I wonder how to address the following question:

Starting from a generic tree, is there an algorithmic way to connect any two nodes of the tree with $M$ unique paths such that no two paths contain the same edge? How can the total number of edges in the modified graph be kept a minimum?

I trying to answer this from a network-engineer's perspective. Any help is appreciated.


Yes. See the paper Minimum augmentation of a tree to a K-edge-connected graph by Ueno, Kajitani and Wada.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.