## 3 Connected Dominating Set
### Algorithm for Unit Line Graphs  
We present a local algorithm for connected dominating set on unit line graphs with locality distance one. It is an extension of the algorithm for dominating set presented in this paper. The approximation ratio of this algorithm is 6.  
Now we present the algorithm in detail. Let \(G=(V,E)\) be a unit line graph. For a vertex \(v\) we denote by \(v_{x}\) its \(x\)-coordinate. As in Algorithm 2 for all integers \(i\) we define \(V_{i}:=\{v\in V|i\leq v_{x}<i+1\}\) and \(H:=\{i|V_{i}\
eq\emptyset\}\). For all \(i\in H\) we define \(v[i]\) and \(v^{\prime}[i]\) to be the vertices with the smallest and largest \(x\)-coordinates in \(V_{i}\). We define \(CD:=\{v[i],v^{\prime}[i]|i\in H\}\). We output \(CD\). We refer to this as Algorithm 4.  
```
1// Algorithm is executed independently by each node \(v\);
2// let \(i\) be the integer such that \(v\in V_{i}\);
3 Find all vertices in \(N(v)\) and determine \(V_{i}\);
4 if\(v=v[i]\) or \(v=v^{\prime}[i]\)then become part of the dominating set \(CD\)else Do not become part of \(CD\)
```  
**Algorithm 4**Local algorithm for finding a connected dominating set in a unit line graph  
We prove the correctness of Algorithm 4 in Theorem 7.  
**Theorem 7**.: _Let \(G\) be a unit line graph. Algorithm 4 has the following properties:_  
1. _The computed set_ \(CD\) _is a connected dominating set for_ \(G\)_._
2. _Let_ \(CD_{OPT}\) _be an optimal connected dominating set. It holds that_ \(|D|\leq 6\cdot|D_{OPT}|\)_._
3. _Whether or not a vertex_ \(v\) _is in_ \(CD\) _depends only on the vertices at most one hop away from_ \(v\)_, i.e. Algorithm_ 4 _is local._
4. _The processing time for a vertex_ \(v\) _is linear in the number of vertices adjacent to_ \(v\)_._  
Proof.: We first prove that \(CD\) is indeed a connected dominating set for \(G\). Let \(i\in H\). Let \(D\) be the dominating set which Algorithm 2 would have computed for \(G\). As \(D\subseteq CD\) it remains to prove that \(CD\) is connected. For all \(i\) it holds that \(v[i]\) and \(v^{\prime}[i]\) are connected by an edge (assuming \(v[i]\
eq v^{\prime}[i]\)). Let \(i\) be an integer such that \(i\in H\) and \(i+1\in H\). Then there are edges connecting \(v^{\prime}[i]\) and \(v[i+1]\) since \(v^{\prime}[i]\) is the vertex on the very right of \(V_{i}\) and \(v[i+1]\) is the vertex on the very left of \(V_{i+1}\) and \(G\) is a connected unit line graph. This proves that \(CD\) is connected.  
Now we prove that for an optimal connecting dominating set \(CD_{OPT}\) it holds that \(|CD|\leq 6\cdot|CD_{OPT}|\). Let \(D\) again be the dominating set which Algorithm 2 would have computed for \(G\). From ourconstruction it follows that \(|CD|\leq 2\cdot|D|\). As \(|D_{OPT}|\leq|CD_{OPT}|\) it follows that  
\[|CD| \leq 2\cdot|D|\] \[\leq 2\cdot 3\cdot|D_{OPT}|\] \[\leq 6\cdot|CD_{OPT}|\]  
Next we determine the locality of Algorithm 4. In the algorithm, a vertex \(v\) in a set \(V_{i}\) only needs to explore all other vertices in \(V_{i}\). (This is sufficient to determine whether \(v\) is the vertex with the smallest \(x\)-coordinate or with the largest \(x\)-coordinate among the vertices in \(V_{i}\).) So whether or not \(v\in CD\) depends only on the vertices which are at most one hop away from \(v\).  
Now we prove the processing time of Algorithm 4. Let \(v\) be a vertex and define \(n_{1}(v):=|N^{1}(v)|\). In the algorithm \(v\) needs to determine for each vertex \(v^{\prime}\in N^{1}(v)\) whether \(v^{\prime}\in V_{i}\) and whether \(v^{\prime}\) has a smaller or a larger \(x\)-coordinate than \(v\). This can be done in \(O\left(n_{1}(v)\right)\) time.