eldorado.tu-dortmund.de/collections/faee6a36-bcd0-4f51-a562-539fd5166b5f
Lehrstuhl V Diskrete Optimierung
(|V|-1)-approximation algorithm for BMST, where |V| is the number of vertices. Moreover, we show that 2-approximating BMST is fixed-parameter tractable and that, in case of uniform costs on leader's edges [...] und Approximationseigenschaften detailliert analysieren. Wir zeigen, dass das Problem NP-schwer und W[2]-schwer ist, im Fall, dass K Teil des Inputs ist, selbst wenn die Menge der zulässigen Lösungen polynomiell [...] multicommodity flow can be represented as a convex combination of unsplittable flows of congestion at most 2. Further, we combine different path restrictions from the ones mentioned above. In the k-splittable …
