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

2020/01/28 by Buchin, Maike, Krivošija, Amer, Neuhaus, Alexander
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2001.10502

Abstract

We give algorithms to compute the Fréchet distance of trees and graphs with bounded tree width. Our algorithms run in O(n²) time for trees of bounded degree, and O(n²√(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.

Related

• Frechet-Like Distances between Two Merge Trees
• Fréchet Distance in Unweighted Planar Graphs
• On the Discrete Fréchet Distance in a Graph
• The k-Fréchet distance
• Distance Measures for Embedded Graphs