4 papers · 1 filter
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
Highway Dimension: a Metric View
Andreas Emil Feldmann, Arnold Filtser
Realistic metric spaces (such as road/transportation networks) tend to be much more algorithmically tractable than general metrics. In an attempt to formalize this intuition, Abrah…
Generalized -Center: Distinguishing Doubling and Highway Dimension
Andreas Emil Feldmann, Tung Anh Vu
We consider generalizations of the -Center problem in graphs of low doubling and highway dimension. For the Capacitated -Supplier with Outliers (CkSwO) problem, we show an ef…
Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
Andreas Emil Feldmann, Michael Lampis
In this paper we reassess the parameterized complexity and approximability of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes a…