In a simple connected graph $G=(V,E)$, a subset of vertices $S \subseteq V$ is a dominating set in graph $G$ if any vertex $v \in V\setminus S$ is adjacent to some vertex $x$ from this subset. It is known that this problem is NP-hard, and hence there exists no exact polynomial-time algorithm that finds an optimal solution to the problem. This work aims to present an exact enumeration and heuristic algorithm that can be used for large-scale real-life instances. Our exact enumeration algorithm begins with specially derived lower and upper bounds on the number of vertices in an optimal solution and carries out a binary search within the successively derived time intervals. The proposed heuristic accomplishes a kind of depth-first search combined with breadth-first search in a solution tree. The performance of the proposed algorithms is far better than that of the state-of-the-art ones. For example, our exact algorithm has solved optimally problem instances with order 300 in 165 seconds. This is a drastic breakthrough compared to the earlier known exact method that took 11036 seconds for the same problem instance. On average, over all the 100 tested problem instances, our enumeration algorithm is 168 times faster.