Parameterized Approximation Algorithms for some Location Problems in Graphs

Arne Leitert, Feodor F. Dragan

We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) $r$-Domination problem and the (Connected) $p$-Center problem for unweighted and undirected graphs. Given a graph $G$, we show how to construct a (connected) $\big(r + \mathcal{O}(\mu) \big)$-dominating set $D$ with $|D| \leq |D^*|$ efficiently. Here, $D^*$ is a minimum (connected) $r$-dominating set of $G$ and $\mu$ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of $G$. Additionally, we show that a $+ \mathcal{O}(\mu)$-approximation for the (Connected) $p$-Center problem on $G$ can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment