• German
German

Main Navigation

Buchin/Krivosija/2020a: Computing the Fr\'echet distance of trees and graphs of bounded tree width

Bibtype Article
Bibkey Buchin/Krivosija/2020a
Author Buchin, Maike and Krivosija, Amer and Neuhaus, Alexander
Title Computing the Fr\'echet distance of trees and graphs of bounded tree width
Journal CoRR
Volume abs/2001.10502
Abstract We give algorithms to compute the Fr\'echet 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\'echet distance in FPT (fixed parameter tractable) time.
Note Presented in EuroCG 2020
Year 2020
Projekt SFB876-A2
Url https://arxiv.org/pdf/2001.10502.pdf
Bibtex Here you can get this literature entry as BibTeX format.