Computing the second and third systoles of a combinatorial surface
Matthijs Ebbens, Francis Lazarus
给定一个胞腔嵌入在拓扑曲面S上的加权无向图G，我们描述了计算G中第二短和第三短闭路径的算法，这些闭路径在S中既不同伦平凡，也不同伦于最短的非平凡闭路径或彼此。我们的算法对于第二短路径运行时间为O(n^2log n)，对于第三短路径为O(n^3)。我们还展示了当亏格和边界数量固定时，如何将第二短非同伦平凡闭路径的运行时间减少到O(nlog n)。我们的算法依赖于对S中前三个最短非同伦平凡曲线的配置的仔细分析。作为中间步骤，我们还描述了如何在O(n^2)时间或O(n^3)时间内分别计算S的给定边界分量的一对顶点之间或所有顶点对之间的最短本质弧。
Given a weighted, undirected graph G cellularly embedded on a topological surface S, we describe algorithms to compute the second shortest and third shortest closed walks of G that are neither homotopically trivial in S nor homotopic to the shortest non-trivial closed walk or to each other. Our algorithms run in O(n^2log n) time for the second shortest walk and in O(n^3) time for the third shortest walk. We also show how to reduce the running time for the second shortest homotopically non-trivia...
