Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination

Ioannis Lamprou, Ioannis Sigalas, Vassilis Zissimopoulos

We consider the \emph{Budgeted} version of the classical \emph{Connected Dominating Set} problem (BCDS). Given a graph $G$ and a budget $k$, we seek a connected subset of at most $…