Metadata about: We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k, we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous [Formula: see text] approximation in [Khuller, Purohit, and Sarpatwar, SODA 2014] by introducing a new method for performing tree decompositions in the analysis of the last part of the algorithm. This new approach provides a [Formula: see text] approximation guarantee. By generalizing the analysis of the first part of the algorithm, we are able to modify it appropriately and obtain a further improvement to [Formula: see text]. On the other hand, we prove a [Formula: see text] inapproximability bound, for any [Formula: see text]. We also examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we are given a graph G, and a budget k, and we seek a, not necessarily connected, subset of k edges such that the number of dominated vertices in G is maximized. We prove there exists a [Formula: see text]-approximation algorithm. Also, for any [Formula: see text], we present a [Formula: see text]-inapproximability result by a gap-preserving reduction from the maximum coverage problem. Finally, we examine the “dual” Partial Edge-Vertex Domination (PEVD) problem, where a graph G and a quota [Formula: see text] are given. The goal is to select a minimum-size set of edges to dominate at least [Formula: see text] vertices in G. In this case, we present a [Formula: see text]-approximation algorithm by a reduction to the partial cover problem.

About: We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k, we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous [Formula: see text] approximation in [Khuller, Purohit, and Sarpatwar, SODA 2014] by introducing a new method for performing tree decompositions in the analysis of the last part of the algorithm. This new approach provides a [Formula: see text] approximation guarantee. By generalizing the analysis of the first part of the algorithm, we are able to modify it appropriately and obtain a further improvement to [Formula: see text]. On the other hand, we prove a [Formula: see text] inapproximability bound, for any [Formula: see text]. We also examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we are given a graph G, and a budget k, and we seek a, not necessarily connected, subset of k edges such that the number of dominated vertices in G is maximized. We prove there exists a [Formula: see text]-approximation algorithm. Also, for any [Formula: see text], we present a [Formula: see text]-inapproximability result by a gap-preserving reduction from the maximum coverage problem. Finally, we examine the “dual” Partial Edge-Vertex Domination (PEVD) problem, where a graph G and a quota [Formula: see text] are given. The goal is to select a minimum-size set of edges to dominate at least [Formula: see text] vertices in G. In this case, we present a [Formula: see text]-approximation algorithm by a reduction to the partial cover problem.

an Entity references as follows:

Graph IRI	Count
http://ns.inria.fr/covid19/graph/entityfishing	10
http://ns.inria.fr/covid19/graph/articles	3

Faceted Search & Find service v1.13.91

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Copyright © 2009-2025 OpenLink Software