论文标题
高于Erdős-Gallai绑定的最长循环
Longest Cycle above Erdős-Gallai Bound
论文作者
论文摘要
1959年，ErdőS和Gallai证明了平均顶点度AD（g）\ GEQ 2的每个图G包含一个至少AD（G）的长度周期。我们提供了一种算法，即时间2^{o（k）} n^{o（1）}在时间2^{o（k）}}中确定2个连接的n-vertex Graph G是否包含长度至少AD（g）+k的周期。这解决了几篇论文中明确提到的一个开放问题。我们算法的主要成分本身是有趣的新图理论结果。
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in time 2^{O(k)} n^{O(1)} decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.
