A Graph-Matching Formulation of the Interleaving Distance between Merge Trees
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913573814403072 |
|---|---|
| author | Pegoraro, Matteo |
| author_facet | Pegoraro, Matteo |
| contents | In this work we study the interleaving distance between merge trees from a combinatorial point of view. We use a particular type of matching between trees to obtain a novel formulation of the distance. With such formulation, we tackle the problem of approximating the interleaving distance by solving linear binary optimization problems in a recursive and dynamical fashion, obtaining lower and upper bounds. We implement those algorithms to compare the outputs with another approximation procedure presented by other authors. We believe that further research in this direction could lead to polynomial time algorithms to approximate the distance and novel theoretical developments on the topic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_15531 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Graph-Matching Formulation of the Interleaving Distance between Merge Trees Pegoraro, Matteo Combinatorics Algebraic Topology In this work we study the interleaving distance between merge trees from a combinatorial point of view. We use a particular type of matching between trees to obtain a novel formulation of the distance. With such formulation, we tackle the problem of approximating the interleaving distance by solving linear binary optimization problems in a recursive and dynamical fashion, obtaining lower and upper bounds. We implement those algorithms to compare the outputs with another approximation procedure presented by other authors. We believe that further research in this direction could lead to polynomial time algorithms to approximate the distance and novel theoretical developments on the topic. |
| title | A Graph-Matching Formulation of the Interleaving Distance between Merge Trees |
| topic | Combinatorics Algebraic Topology |
| url | https://arxiv.org/abs/2111.15531 |