论文标题
计数次指数时间平面图上的周期
Counting Cycles on Planar Graphs in Subexponential Time
论文作者
论文摘要
我们研究了在三角形平面图上计算所有周期或自我避免步行（锯）的问题。我们提出了一个$ 2^{o（\ sqrt {n}）} $ time Algorithm，用于此计数问题。在该算法中使用的技术成分中，有平面分离器定理以及使用成对的Motzkin路径和Motzkin数字进行精致的分析。然后，我们可以在次指数时间内将该算法调整为均匀样品锯。我们的工作是出于整理区域地图的问题所激发的。
We study the problem of counting all cycles or self-avoiding walks (SAWs) on triangulated planar graphs. We present a subexponential $2^{O(\sqrt{n})}$ time algorithm for this counting problem. Among the technical ingredients used in this algorithm are the planar separator theorem and a delicate analysis using pairs of Motzkin paths and Motzkin numbers. We can then adapt this algorithm to uniformly sample SAWs, in subexponential time. Our work is motivated by the problem of gerrymandered districting maps.
