Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Designing Caterpillars for Graphs: Approximation and Hardness
Leon Kullmann, Phuoc Lucky Trinh, Leon Kellerhals +3
The classical Minimum Linear Arrangement (MLA) problem has been studied extensively. It is known to be NP-hard and it admits an -approximation [Feige an…
cs.DS2026
Designing Approximate Binary Trees for Trees
Leon Kellerhals, Mitja Krebs, André Nichterlein +1
We study the following problem that is motivated by demand-aware network design: Given a tree~, the task is to find a binary tree~ on the same vertex set. The objective is to…