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

preprint2020arXivOpen access

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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

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

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0