## 4 Computational Study of PTAS
Notice that the branchwidth of every \((k+2)\)-outer planar graph is at most \(2(k+2)\). Hence, by increasing \(k\) the size of subgraphs and their branchwidth will increase. Theoretical results suggest that increasing \(k\) gives smaller approximated solutions for minimization problems. Our computing results confirm the theoretical analysis of the \(k\)-outer planar decomposition method. For example, for \(k=4\), every instance can be decomposed into subgraphs with a branchwidth of at most 12. This is the largest value of branchwidth that can be processed on our computational platform in a practical time. Since the theory of NP-completeness has reduced hopes that NP-hard problems can be solved in polynomial time, heuristic and approximation algorithms have attracted more attentions. These algorithms compute near optimal solutions within a reasonable time for problems of practical size. We compare the performance of the PTAS with the performance of three different heuristic algorithms introduced in [22] for the planar dominating set problem. In what follows we briefly explain these heuristic algorithms (for more details please refer to [22]). In [22], six heuristic algorithms for the dominating set problem are studied. We test the performance of these six methods, but only report three of them with better performances. The three reported heuristics are described below. Let \(D\) be a dominating set computed by these heuristics. _Greedy_: Initially, \(D\) is empty. In each iteration, a vertex which dominates a maximum number of vertices in \(V(G)\setminus D\) is added to \(D\). _Greedy-Rev_: Initially \(D=V(G)\). In each iteration, a vertex is removed from \(D\), such that the resulting set remains a dominating set of \(G\). A vertex is chosen to be removed, by ordering the vertices of \(D\) in increasing node degree, and removing the first vertex that does not dominate any vertex uniquely. \begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline  & **Graph** & \(|E(G)|\) & \(bw\) & \multicolumn{3}{c|}{**Exact Alg. **} & \multicolumn{3}{c|}{**k = 3**} & \multicolumn{3}{c|}{**k = 4**} \\ \cline{4-13}  & \(G\) & & & \(\gamma(G)\) & \(\beta\) & **time** & \(D_{PTAS}\) & \(\beta\) & **time** &  
_Greedy-Vote:_ Initially, \(D\) is empty. This algorithm does not include a vertex \(u\) in \(D\) only based on the number of vertices which are dominated by \(u\). It uses a more complex voting scheme to select a vertex to be included. We omit the details of the selection scheme and readers may refer to [22] for details. We study the performances of the above heuristic algorithms for the four classes of planar graphs that are used in the study of the PTAS. These heuristic algorithms are implemented in C++. Table 2 shows the computational results of these heuristic algorithms and the PTAS. In Table 2, \(D_{Gr},D_{Rev}\), and \(D_{Vote}\) are the sizes of dominating sets computed by the heuristic algorithm Greedy, Greedy-Rev, and Greedy-Vote, respectively. For every graph instance, if the size of the instance allows the application of the FT algorithm, we include the size of the minimum dominating set of the instance, as well. For the PTAS, we include the best result \(D_{PTAS}\) for every instance from Table 1. Time in the table is in seconds. \begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline  & **Graph** & \(|\mathbf{E(G)}|\) & \(\gamma(G)\) & \multicolumn{2}{c|}{**Greedy Alg. **} & \multicolumn{2}{c|}{**Greedy-Rev Alg. **} & \multicolumn{2}{c|}{**Greedy-Vote Alg. **} & \multicolumn{2}{c|}{**PTAS**} \\ \cline{4-13}  & \(\mathbf{G}\) & & & \(\mathbf{D_{Gr}}\) & **time** & \(\mathbf{D_{Rev}}\) & **time** & \(\mathbf{D_{Vote}}\) & **time** & \(\mathbf{D_{PTAS}}\) & **time** \\ \  
The results in the table show that the heuristic algorithms are always faster than the PTAS. However, the size of dominating sets computed by the heuristics are larger than those by the PTAS for most of instances.