DocumentCode :
130887
Title :
A faster approximate method to identify minimum dominating set
Author :
You Zhou ; Guodong Lv ; Baoxin Xiu ; Weiming Zhang ; Qing Cheng
Author_Institution :
Sci. & Technol. on Inf. Syst. Eng. Lab., Nat. Univ. of Defense Technol., Changsha, China
fYear :
2014
fDate :
27-29 June 2014
Firstpage :
443
Lastpage :
448
Abstract :
The minimum dominating set (MDS) problem is known to be NP-hard. Compared with the currently fastest extract algorithm for MDS problem on graphs of n vertices using O(20.59n)time, which could merely tackle these problems with 200 vertices scale in 8 hours, the paper presents a faster approximate layer-method to address MDS problems in O(n2) time and the method is proved to be effective particularly for larger scale MDS. Furthermore, the programming phases are shown in detail.
Keywords :
computational complexity; graph theory; set theory; MDS problem; NP-hard problem; O(20.59n) time; O(n2) time; approximate layer-method; graphs; minimum dominating set problem; Accuracy; Algorithm design and analysis; Approximation algorithms; Educational institutions; Greedy algorithms; Labeling; Time complexity; Minimum dominating set; layer method; network;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Software Engineering and Service Science (ICSESS), 2014 5th IEEE International Conference on
Conference_Location :
Beijing
ISSN :
2327-0586
Print_ISBN :
978-1-4799-3278-8
Type :
conf
DOI :
10.1109/ICSESS.2014.6933601
Filename :
6933601
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=130887
بازگشت