论文标题
$ 2^{o（k）} n $算法，用于$ k $ cycle in Binallaped Graph系列
A $2^{O(k)}n$ algorithm for $k$-cycle in minor-closed graph families
论文作者
论文摘要
令$ {\ Mathcal C} $为适当的次要图形系列。我们提出了一种随机算法，该算法在{\ Mathcal c} $中给出了图形$ g \带有$ n $ vertices，在$ 2^{o（k）} n $ time中找到了一个简单的$ k $中的简单周期$ k $（如果存在）。该算法适用于有向和无向图。在此问题的先前线性时间算法中，对$ k $的运行时依赖性是超级指数。该算法可以被取代，得出$ 2^{o（k）} n \ log n $ time算法。
Let ${\mathcal C}$ be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph $G \in {\mathcal C}$ with $n$ vertices, finds a simple cycle of size $k$ in $G$ (if exists) in $2^{O(k)}n$ time. The algorithm applies to both directed and undirected graphs. In previous linear time algorithms for this problem, the runtime dependence on $k$ is super-exponential. The algorithm can be derandomized yielding a $2^{O(k)}n\log n$ time algorithm.
