中文版 英文版
 
   
 
  首 页 中心概况 新闻动态 学术活动 交流合作
 
 
 当前位置:首页 -> 学术活动 -> 学术报告
 
名 称 吴文俊数学重点实验室组合图论系列讲座之四十六【谢孙源 教授】
题 目 The Internal Steiner Tree Problem: Hardness and Approximations
报告人 谢孙源
时 间 0000-00-00 下午 16:30-17:30
地 点 管理科研楼1208会议室
详 细

 题 目:The Internal Steiner Tree Problem: Hardness and Approximations


报告人:谢孙源,教授(台湾成功大学)


时 间:2014年10月28日(星期二) 下午 16:30-17:30


地 点:管理科研楼1208会议室


摘要:Given a graph G = (V, E) with a cost function c: E → R+ and a vertex subset R⊂V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves findingan internal Steiner tree T whose total cost is the minimum. This talk first shows that the internal Steinertree problem is MAX SNP-hard, then presents a (2ρ + 1)-approximation algorithm for solving the problem on complete graphs, where ρ is an approximation ratio for the Steiner tree problem. Currently, the best-known ρ is  . Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, this talk presents a 9/7-approximation algorithm for the problem.

报告人简介:台湾大学博士,成功大学特聘教授,制造资讯与系统研究所所长;研究方向涉及算法、图论、互连网络、多处理机系统、平行及分散系统、生物信息等领域,共发表94篇期刊和51篇会议论文,其中在IEEE Transactions 上的论文超过30篇;担任Theoretical Computer Science, Journal of Information Security,Journal of Supercomputing 等10多种国际专业杂志编委;荣获IEEE Outstanding Technical Achievement Award,英国资讯学会会士,成功大学教学杰出教师,台湾李国鼎研究奖,台湾杰出研究奖,台湾杰出电机工程教授奖和杰出资讯人才奖。

主办单位:
中国科学技术大学数学科学学院
中科院吴文俊数学重点实验室
欢迎感兴趣的师生参加!

 
 
  欢迎访问中国科学院国家数学与交叉科学中心(合肥)
地址:合肥金寨路96号中国科技大学数学科学学院 邮编:230026 电话: 0551-3600206 Fax: 0551-3601005 邮箱: ncmis@ustc.edu.cn