1. Αποθετήριο Παραδοτέων Υποτρόφων Δράσεων ΕΣΠΑ Τριτοβάθμιας Εκπαίδευσης 2017-2023
2. Όλο το Αποθετήριο
3. Μεταδιδακτορικοί ερευνητές

Τύπος:	Άρθρο σε επιστημονικό περιοδικό
Τίτλος:	Improved budgeted connected domination and budgeted edge-vertex domination
Συγγραφέας:	[EL] Λάμπρου, Ιωάννης[EN] Lamprou, Ioannis [EL] Σιγάλας, Ιωάννης[EN] Sigalas, Ioannis [EL] Ζησιμόπουλος, Βασίλειος[EN] Zissimopoulos, Vassilis
Ημερομηνία:	22/01/2021
Περίληψη:	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 (1 − e−1)/13 state of the art [Khuller, Purohit, and Sarpatwar, SODA 2014] by introducing a new method for performing tree decompositions in the analysis of the algorithm. This new approach provides a (1 − e−1)/12 approximation guarantee. By generalizing the analysis, we are able to obtain a further improvement to (1 − e−7/8)/11. On the other hand, we prove a (1 − e−1 + ) inapproximability bound, for any > 0, holding also if the subset is required to have a star as a subgraph. In the latter case, we design another algorithm with a matching (1 − e−1) approximation guarantee. Also, we examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we seek a (not necessarily connected) subset of k edges maximizing the number of dominated vertices in G. We prove a (1−e−1)-approximation and a (1−e−1 +)-inapproximability by reductions to/from the maximum coverage problem. Finally, we study the “dual” Partial EdgeVertex Domination (PEVD) problem, and we present a log-approximation by a reduction to the partial cover problem.
Γλώσσα:	Αγγλικά
Σελίδες:	12
DOI:	10.1016/j.tcs.2021.01.030
EISSN:	1879-2294
Θεματική κατηγορία:	[EL] Επιστήμη ηλεκτρονικών υπολογιστών[EN] Computer Science
Λέξεις-κλειδιά:	Approximation; Budget; Partial; Connected domination; Edge-Vertex Domination
Κάτοχος πνευματικών δικαιωμάτων:	© 2021 Elsevier B.V. All rights reserved.
Ηλεκτρονική διεύθυνση του τεκμηρίου στον εκδότη:	https://www.sciencedirect.com/science/article/pii/S0304397521000529
Ηλεκτρονική διεύθυνση περιοδικού:	https://www.sciencedirect.com/journal/theoretical-computer-science
Τίτλος πηγής δημοσίευσης:	Theoretical Computer Science
Τόμος:	858
Σελίδες τεκμηρίου (στην πηγή):	1-12
Σημειώσεις:	This research is co-financed by Greece and the European Union (European Social Fund - ESF) through the Operational Programme “Human Resources Development, Education and Lifelong Learning” in the context of the project “Reinforcement of Postdoctoral Researchers - 2nd Cycle” (MIS-5033021), implemented by the State Scholarships Foundation (IKY).
Εμφανίζεται στις συλλογές:	Μεταδιδακτορικοί ερευνητές