| Abstract: |
In this talk, we present some new problems how to construct some combinatorial structures required in networks or graphs. We can consider the new general model: a network (simply, a graph) G=(V, E; w) and a kind material with length L, where a length function w: E→R+, and for each edge e=uv ? E, when the length w(u,v) ≦ L holds, the two vertices u and v may be connected by a part (or fullness) of such a kind material if needing, otherwise the vertices u and v can never be connected by such a kind material. For a fixed combinatorial structure P, it is asked how to construct a (spanning) subnetwork G' from the original network G to ensure G' maintaining such a structure P, the objective is to minimize the number of pieces of such a material used in the (spanning) subnetwork G'. For different combinatorial structures, we can present some approximation algorithms to solve them, respectively. |
|---|