Designing Approximate Binary Trees for Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908987351367680 |
|---|---|
| author | Kellerhals, Leon Krebs, Mitja Nichterlein, André Schmid, Stefan |
| author_facet | Kellerhals, Leon Krebs, Mitja Nichterlein, André Schmid, Stefan |
| contents | We study the following problem that is motivated by demand-aware network design: Given a tree~$G$, the task is to find a binary tree~$H$ on the same vertex set. The objective is to minimize the sum of distances in~$H$ between vertex pairs that are adjacent in~$G$. We present a linear-time factor-4 approximation for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_20786 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Designing Approximate Binary Trees for Trees Kellerhals, Leon Krebs, Mitja Nichterlein, André Schmid, Stefan Data Structures and Algorithms We study the following problem that is motivated by demand-aware network design: Given a tree~$G$, the task is to find a binary tree~$H$ on the same vertex set. The objective is to minimize the sum of distances in~$H$ between vertex pairs that are adjacent in~$G$. We present a linear-time factor-4 approximation for this problem. |
| title | Designing Approximate Binary Trees for Trees |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.20786 |