We show that there is a deterministic local algorithm (constant-time distributed graph
algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs …

In this paper, we propose a distributed algorithm for the minimum dominating set problem.
For some especial networks, we prove theoretically that the achieved answer by our …

We show how to compute an (11+ ϵ)-approximation of a minimum dominating set in a
planar graph in a constant number of rounds in the LOCAL model of distributed computing …

In this paper, we consider a variant of dominating set problem, ie, the total dominating set
problem. Given an undirected graph G=(V, E), a subset of vertices T⊆ V is called a total …

We provide a deterministic CONGEST algorithm to constant factor approximate the minimum
dominating set on graphs of bounded arboricity in $ O (\log n) $ rounds. This improves over …

We consider the massively parallel computation (MPC) model, which is a theoretical
abstraction of large-scale parallel processing models such as MapReduce. In this model …

We show that the dominating set problem admits a constant factor approximation in a
constant number of rounds in the LOCAL model of distributed computing on graph classes …

This document is an informal bibliography of the papers dealing with distributed
approximation algorithms. A classic setting for such algorithms is bounded degree graphs …

Given a network graph G=(V, E), a subset T⊆ V is said to be a total dominating set (TDS) if
every v∈ V is adjacent to at least one node in T. In this paper, we present a distributed …

In this paper, we study the minimum dominating set (MDS) problem and the minimum total
dominating set MTDS) problem which have many applications in real world. We propose a …