| Bibtype |
Article |
| Bibkey |
Buchin/Krivosija/2020a |
| Author |
Buchin, Maike and Krivo\v{s}ija, 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 |
