Designing Approximate Binary Trees for Trees
2026-04-22 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors look at a problem where you start with a tree network and want to create a new binary tree using the same points. Their goal is to make sure that points directly connected in the first tree are still close together in the new binary tree. They developed a method that quickly finds a new binary tree that is at most four times worse than the best possible arrangement. This approach works efficiently in time proportional to the size of the network.
treebinary treenetwork designapproximation algorithmdistancevertexedgelinear-timefactor-4 approximationdemand-aware network
Authors
Leon Kellerhals, Mitja Krebs, André Nichterlein, Stefan Schmid
Abstract
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.