Improving Efficiency of Minimum Dominating Set Problem using Simulated Annealing Algorithms 


Vol. 18,  No. 2, pp. 69-74, Apr.  2011
10.3745/KIPSTA.2011.18.2.69


PDF
  Abstract

The minimum dominating set problem of a graph G is to find a smallest possible dominating set. The minimum dominating set problem is a well-known NP-complete problem such that it cannot be solved in polynomial time. Heuristic or approximation algorithm, however, will perform well in certain area of application. In this paper, we suggest three different simulated annealing algorithms and experimentally show better efficiency improvement by applying these algorithms to the graph instances developed by DIMACS.

  Statistics
  Cite this article

[IEEE Style]

T. E. Jeong, "Improving Efficiency of Minimum Dominating Set Problem using Simulated Annealing Algorithms," The KIPS Transactions:PartA, vol. 18, no. 2, pp. 69-74, 2011. DOI: 10.3745/KIPSTA.2011.18.2.69.

[ACM Style]

Tae Eui Jeong. 2011. Improving Efficiency of Minimum Dominating Set Problem using Simulated Annealing Algorithms. The KIPS Transactions:PartA, 18, 2, (2011), 69-74. DOI: 10.3745/KIPSTA.2011.18.2.69.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals