Designing Approximate Binary Trees for Trees

Authors: Leon Kellerhals, Mitja Krebs, André Nichterlein, Stefan Schmid

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.