Improved budgeted connected domination and budgeted edge-vertex domination

DOI10.1016/j.tcs.2021.01.030zbMath1462.68241arXiv1907.06576OpenAlexW2958617377MaRDI QIDQ2222087

Ioannis Sigalas, Ioannis Lamprou, Vassilios Zissimopoulos

Publication date: 3 February 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1907.06576

zbMATH Keywords

approximation algorithmsbudgetedge-vertex dominationconnected domination

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (2)

In memory of Jérôme Monnot ⋮ Edge-vertex domination in trees

Cites Work

• Unnamed Item
• Unnamed Item
• Improved performance of the greedy algorithm for partial cover
• Connected dominating set. Theory and applications
• The algorithmic complexity of mixed domination in graphs
• Approximation algorithms for connected dominating sets
• The budgeted maximum coverage problem
• An improved upper bound of edge-vertex domination number of a tree
• On the mixed domination problem in graphs
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Coverage problems in sensor networks
• Bin Packing with Colocations
• Minimum Edge Dominating Sets
• A threshold of ln n for approximating set cover
• Saving an epsilon
• Edge Dominating Sets in Graphs
• Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems
• Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
• Vertex-edge domination in graphs

This page was built for publication: Improved budgeted connected domination and budgeted edge-vertex domination