论文标题
计算树木和有限树宽度的图形的距离
Computing the Fréchet distance of trees and graphs of bounded tree width
论文作者
论文摘要
我们提供算法来计算树木和有界树宽度的树木的距离。我们的算法以$ o（n^2）为有限度的树和$ o（n^2 \ sqrt {n \ log n}）$的时间运行。对于有界树宽度的图形，我们显示可以在FPT（固定参数可拖动）时间中计算Fréchet距离。
We give algorithms to compute the Fréchet distance of trees and graphs with bounded tree width. Our algorithms run in $O(n^2)$ time for trees of bounded degree, and $O(n^2\sqrt{n \log n})$ time for trees of arbitrary degree. For graphs of bounded tree width we show one can compute the Fréchet distance in FPT (fixed parameter tractable) time.
