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.DS2024
SpiderDAN: Matching Augmentation in Demand-Aware Networks
Aleksander Figiel, Darya Melnyk, André Nichterlein +2
Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication…