我系本科生论文被Theoretical Computer Science录用

2011.06.07 00:00

6月6日,本科生计74的张文琦与其指导教师刘永进合作完成的论文《网格图中的近似最长路径》(Approximating the Longest Paths in Grid Graphs),被Theoretical Computer Science期刊录取为长文。

论文针对网格图中最长路径求解这一NP-hard问题,提出了一个高效近似算法,可以在O(n2)时间内找到一条长度不小于(5n/6)+2的路径,其中n为网格图的顶点数。之前最好的算法只能找到长度为O((logn/loglogn)2)的路径,且时间复杂度为O(n3)。

Theoretical Computer Science为理论计算机科学领域内知名期刊,2009年SCI影响因子0.943。

关闭

Baidu
sogou