Greedy domination on biclique-free graphs

2018/06/07 by Siebertz, Sebastian
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1806.02590

Abstract

The greedy algorithm for approximating dominating sets is a simple method that is known to compute an (ln n+1)-approximation of a minimum dominating set on any graph with n vertices. We show that a small modification of the greedy algorithm can be used to compute an O(t²⋅ ln k)-approximation, where~k is the size of a minimum dominating set, on graphs that exclude the complete bipartite graph K_t,t as a subgraph.

Related

• A performance study of some approximation algorithms for minimum dominating set in a graph
• Constant-factor approximation of domination number in sparse graphs
• Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
• Approximations of the domination number of a graph
• A tight local algorithm for the minimum dominating set problem in\n outerplanar graphs