科研动态

涂建华副教授在《DISCUSS. MATH. GRAPH. T.》发表学术研究论文

发文时间:2019-08-25

  20193月万豪国际娱乐网网址新版万豪app下载学部涂建华副教授(第一作者)与南开大学史永堂教授(通讯作者)合作在国际SCI期刊《DISCUSS. MATH. GRAPH. T.》上发表了题为“AN EFFICIENT POLYNOMIAL TIME APPROXIMATION SCHEME FOR THE VERTEX COVER P3 PROBLEM ON PLANAR GRAPHS”的研究论文。

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

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

算法的整体结构