报告地点：腾讯会议ID：572 264 8674
报告人：谭学厚
主办单位：计算机与信息技术学院
报告人简介：
谭学厚，大连海事大学讲座教授，并曾于1985年至1987年任教于南京大学计算机科学系。谭学厚教授1982年毕业于南京大学计算机科学系，1985年获南京大学计算机科学系硕士学位，1991年获日本名古屋大学工学部情报工学科博士学位。1992年至1993年在加拿大麦吉尔大学和蒙特利尔大学博士后工作站工作。谭学厚教授的主要研究方向是计算几何，算法分析与设计，图论和组合优化，主持JSPS项目6项，在Theoretical Computer Science，Algorithmica, Computational Geometry: Theory and Applications，Discrete Applied Mathematics, Journal of Combinatorial Optimization等理论计算机领域内知名期刊和会议发表学术论文50余篇。
报告简介：
众所周知，TSP(traveling salesman problem)问题是一个NP难问题，但如果要访问的点有序或部分有序，很多情况下就有多项式时间的解。该报告将综述近期关于遍历平面多边形区域内线段序列和凸多边形序列的相关工作。包括将巡视员路径问题(即巡视员沿一条最短路径看到多边形内部所有的点)，转化为遍历多边形内部的一个弦序列的问题；求解最短遍历路径的一个有趣的数据结构，最短路径图谱；时间复杂度为O(n^4)和O(n^5)的(无序)直线和射线遍历算法等内容。
版权所有：辽宁师范大学科研处 技术支持：