中国科大学位与研究生教育
课程名称: 教师:
当前位置:
 >> 
 >> 
标签割问题的近似算法和近似困难性
标签割问题的近似算法和近似困难性
教师介绍

本讲教师:张鹏
所属学科:理科
人  气:131

课程介绍
摘要:标签s-t割问题是在信息安全和计算机网络等领域中提出的一个组合优化问题。给一个图,边上有标签,该问题询问最少数目的标签,使得在图上把具有这些标签的边去掉后,能够将给定的源点s和目标点t断开。容易看出,标签s-t割问题是经典的最小s-t割问题的推广。 在本报告中,我们主要介绍标签s-t割问题的两个纯组合算法。这两个算法的近似比分别为O(m1/2)和O(n2/3),其中m和n分别为图上的边数和点数。这是标签s-t割问题当前已知最好的近似比。 报告人简介:张鹏,山东大学软件学院副教授。2007年7月于中科院软件所取得博士学位,长期以来从事组合优化和近似算法的研究工作。在Algorithmica、ToCS、TCS、DAM等主流国际期刊,以及LATIN、ISAAC、COCOON等主流国际会议发表论文40多篇,其中第一作者SCI论文13篇,通讯作者SCI论文3篇。主持国家自然科学基金面上项目两项。

评论

针对该课程没有任何评论,谈谈您对该课程的看法吧?
  • 用户名: 密 码:
致谢:本课件的制作和发布均为公益目的,免费提供给公众学习和研究。对于本课件制作传播过程中可能涉及的作品或作品部分内容的著作权人以及相关权利人谨致谢意!
课件总访问人次:19803900
中国科学技术大学研究生网络课堂试运行版,版权属于中国科学技术大学研究生院。
本网站所有内容属于中国科学技术大学,未经允许不得下载传播。
地址:安徽省合肥市金寨路96号;邮编:230026。TEL:+86-551-63602929;E-mail:wlkt@ustc.edu.cn。