Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph.

In a minimum general partial dominating set problem (MinGPDS), given a graph G = (V , E) , a profit function p : V → R + and a threshold K , the goal is to find a minimum subset of vertices D ⊆ V such that the total profit of those vertices dominated by D is at least K (a vertex is dominated by D if it is either in D or has at least one neighbor in D). In a maximum general budgeted dominating set problem (MaxGBDS), given a budget B , the goal is to find a vertex set D with at most B vertices such that the total profit of those vertices dominated by D is as large as possible. We present the first parallel algorithms for MinGPDS and MaxGBDS in unit disk graphs. They both run in O (log ⁡ n) rounds on O (n) machines, and achieve constant approximation ratios. • First parallel algorithms for minimum partial dominating set and maximum budgeted dominating set in unit disk graphs. • Constant approximation ratios are obtained in logarithmic rounds. • Overcome the challenge brought by the ̀̀partial" consideration by implementing a greedy idea in a parallelized manner. [ABSTRACT FROM AUTHOR]