Given a undirected weighted graph. I would like to find a finite set of paths (consecutive vertices and edges)

  1. each shorter than L

  2. any two vertices can be reached through at most N(in my case N=4) such paths.(paths can be linked halfway, i.e. not necessarily through the begin/end vert).

and the total length of my path set is as small as possible.

In general, I'd like to know if there are relevent theories or algorithms that I can apply to my specific data set.

Thanks in advance for any thought or direction!

  • $\begingroup$ The set of all maximal geodesic paths will certainly do this but there are many. A smaller set is a set of geodesics joining any pair of vertices. $L=N$ is in both cases the diameter. $\endgroup$ – Roland Bacher May 29 '15 at 11:40

Your Answer

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

Browse other questions tagged or ask your own question.