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 || |