## 4 Computational Study of PTAS
Based on our computational results, the Greedy algorithm gives the smallest dominating sets compared to other heuristic algorithms. Table 3 shows the results of our computational study for the FT algorithm, Greedy (the best heuristic method) and PTAS for graph instances whose branchwidths are small enough to run the FT algorithm. Since the branchwidth of graphs in Class(1) grow quickly in the size of graphs, we have only included small instances of this class in Table 3. From the results of the table, we recommend the FT algorithm for optimal solutions if the branchwidth of a graph in Class (1) is smaller than 14. For the instances of Class (2), FT Algorithm is time consuming. If the running time is the driving factor, we suggest the Greedy algorithm for this class of graphs. For the instances of Classes (3) and (4), as the results in Table 3 suggest, the sizes of dominating sets computed by Greedy are considerably bigger than those computed by the PTAS. Moreover, the FT algorithm is time consuming, rendering the PTAS a better choice. For instance, for graph instance rand20000 with 35,975 edges, the FT algorithm takes almost four hours to compute the size of an optimal dominating set (not the set itself), while the PTAS computes a dominating set of a slightly larger size than the optimal value in less than two hours. Table 4 shows the computational results for the instances that the FT algorithm is not able to find an optimal solution in practical time and memory space. The computational results show that for all of these \begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline  & \multicolumn{1}{c|}{**Graph**} & \multicolumn{1}{c|}{\(|E(G)|}\) & \multicolumn{2}{c|}{**Exact Alg.**} & \multicolumn{2}{c|}{**Greedy Alg.**} & \multicolumn{2}{c|}{**PTAS**} \\ \cline{3-10}  & \(G\) & & \(\gamma(G)\) & **time** & \(D_{G}\) & **time** & \(D_{PTAS}\) & **time** \\ \hline (1) & kroB150 & 436 & 23 & 10 & 27 & 0.002 & 28 & 2.08 \\ \cline{2-10}  & pr299 & 864 & 47 & 37 & 54 & 0.032 & 56 & 11.42 \\ \cline{2-10}  & tsp225 & 622 & 37 & 110 & 49 & 0.153 & 46 & 5.21 \\ \cline{2-10}  & a280 & 788 & 43 & 337 & 51 & 0.004 & 51 & 12.09 \\ \hline \hline (2) & tri2000 & 5977 & 321 & 198 & 365 & 0.116 & 361 & 175.59 \\ \cline{2-10}  & tri4000 & 11969 & 653 & 1903 & 729 & 0.183 & 724 & 733.06 \\ \cline{2-10}  & tri6000 & 17979 & 975 & 3576 & 1118 & 0.418 & 1136 & 1994.53 \\ \cline{2-10}  & tri8000 & 23975 & 1283 & 7750 & 1449 & 0.715 & 1430 & 2858.63 \\ \cline{2-10}  & tri10000 & 29976 & 1606 & 16495 & 1819 & 1.117 & 1804 & 4977.06 \\ \hline \hline (3) & rand6000 & 10293 & 1563 & 150 & 1932 & 0.748 & 1658 & 104.85 \\ \cline{2-10}  & rand10000 & 17578 & 2535 & 869 & 3197 & 2.06 & 2692 & 432.23 \\ \cline{2-10}  & rand15000 & 26727 & 3758 & 2769 & 4698 & 4.861 & 4144 & 1313.14 \\ \cline{2-10}  & rand16000 & 28624 & 4002* & 5917 & 5039 & 5.176 & 4295 & 2027.7 \\ \cline{2-10}  & rand20000 & 35975 & 4963* & 13993 & 6273 & 8.053 & 5398 & 5017.02 \\ \hline \hline (4) & Gab500 & 949 & 115 & 238 & 146 & 0.006 & 129 & 18.95 \\ \cline{2-10}  & Gab600 & 1174 & 135* & 3074 & 168 & 0.007 & 156 & 22.10 \\ \cline{2-10}  & Gab700 & 1302 & 162* & 5710 & 200 & 0.01 & 183 & 24.30 \\ \hline \end{tabular}
\end{table} 
Table 3: Computational results for Exact, Greedy and PTAS algorithms for small instances (time in seconds). instances, except one, the \(D_{PTAS}\) is smaller than \(D_{Gr}\). In summary, for applications with running-time priority, Greedy is a better choice to compute an approximated dominating set, and if the running-time is not a big concern, the PTAS is a better option for instances whose optimal dominating set cannot be computed by the FT algorithm in a practical time.