Computing the Fréchet distance of trees and graphs of bounded tree width
Maike Buchin, Amer Krivošija, Neuhaus, Alexander · arXiv (Cornell University) · 2020
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.