On the structure of minimum-weight k-connected spanning networks

Let $$k\ge 2, p\ge 1, q\ge 0$$kź2,pź1,qź0 be integers. We prove that every $$(4kp-2p+2q)$$(4kp-2p+2q)-connected graph contains p spanning subgraphs $$G_i$$Gi for $$1\le i\le p$$1≤i≤p and q spanning trees such that all $$p+q$$p+q subgraphs are pairwise ...

An efficient heuristic is presented for the problem of finding a minimum-size k-connected spanning subgraph of an (undirected or directed) simple graph G=( V, E). There are four versions of the problem, and the approximation guarantees are as follows: ...

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning ...