Seminar on Combinatorics
主講者: 李建平教授(雲南大學)
講題: Some Approximation Algorithms for Constructing Combinatorial Structures Required
時間: 2012-02-03 (Fri.)  14:00 - 15:30
地點: 數學所 722 研討室 (台大院區)
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.
  || Close window ||