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.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • 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.
Subject
  • Algorithms
  • Graph theory
  • Mathematical logic
  • Theoretical computer science
  • Basic concepts in set theory
  • Computational problems in graph theory
  • Computational complexity theory
  • Graph connectivity
  • Approximation algorithms
  • Relaxation (approximation)
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
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)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software