2019年3月数理学院数学学部涂建华副教授（第一作者）与南开大学史永堂教授（通讯作者）合作在国际SCI期刊《DISCUSS. MATH. GRAPH. T.》上发表了题为“AN EFFICIENT POLYNOMIAL TIME APPROXIMATION SCHEME FOR THE VERTEX COVER P3 PROBLEM ON PLANAR GRAPHS”的研究论文。

　　本论文研究了经典的顶点覆盖问题的一类推广，顶点覆盖k-路问题。此问题的提出源于几类实际工程应用，包括有无线传感器加密与交通摄像头设置等问题。k》3时的顶点覆盖k-路所对应的判定问题在二部图和平面图上都是NP-完全的，所以研究这类问题的近似算法有着很重要的理论和实际意义。并且，k》3时顶点覆盖k-路问题在一般图上都没有PTAS。通过对平面图做结构分解，并借助branch—Width等工具，我们设计了平面图上顶点覆盖3-路问题的PTAS，PTAS能让应用者根据实际情况来平衡算法的近似比与时间复杂度，它的给出对问题的求解具有很强的应用价值，也丰富了该问题的复杂性理论结果。

原文链接：https://www.dmgt.uz.zgora.pl/publish/view_pdf.php?ID=-968

算法的整体结构