I am trying to find an algorithm to find a k-connected spanning subgraph of a mulitiple graph (each pair of vertices can be connected via more than 1 direct edge), from a multiple complete graph, with the most minimum sum of capacity.
**k-connected graph: If you remove randomly k-1 vertices from that graph, it will be still connected.
**each edge contains only one capacity, which is an interger.
As you know, with k= 1, we have the Trim algorithm to find the minimal spanning tree. And my idea for k = 2 is to connect one particular vertice (called source) to all of the leaves in the spanning tree from Trim, or even double the edges between each pair of that tree.
Actually, to be exact, my problem is to solve that in a complete multiple graph satisfying the triangle inequality of capacities of edges. However, it didn’t go anywhere and I want to know more in cases of k>=3
yoursmileeeeee is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.