Computing the Fréchet distance of trees and graphs of bounded tree width

01/28/2020
by   Maike Buchin, et al.
0

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√(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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset