2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .