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 $O(\sqrt{\log n}\log \log n)$-approximation [Feige an…