In this paper we will give two distributed approximation algorithms (in the Local model) for the minimum dominating set problem. First we will give a distributed algorithm which finds a dominating set D of size O(gamma(G)) in a graph G which has no topological copy of K_h. The algorithm runs L_h rounds where L_h is a constant which depends on h only. This procedure can be used to obtain a distributed algorithm which given epsilon>0 finds in a graph G with no K_h-minor a dominating set D of size at most (1+epsilon)gamma(G). The second algorithm runs in O(log^*{|V(G)|}) rounds.

In research on distributed local algorithms it is commonly assumed that each vertex has a unique identifier in the entire graph. However, it turns out that in the case of certain classes of graphs (for example not lift-closed bounded degree graphs) identifiers are unnecessary and only a port ordering is needed [4]. One of the open issues was whether identifiers are essential in planar graphs. In this paper, we partially answer this question and we propose an algorithm which returns constant approximation of the MDS problem in the CONGEST model. The algorithm does not use any additional information about the structure of the graph and the nodes do not have unique identifiers. We hope that this paper will be helpful as a hint for further comparisons of the unique identifier model and the model with only a port numbering in other classes of graphs.

We give an efficient distributed algorithm that finds an almost optimal packing of a graph H in a planar graph G. The algorithm is deterministic and its running time is poly-logarithmic in the order of G.