Vol. 25 No.1 | pp.89-96.

Algorithm for Minimum Spanning Tree-Based Backbone Set of Minimum Weighted Connected Dominating Set Problem

Abstract This paper proposes an algorithm to find the exact solution of polynomial time for the minimum weighted connected dominating set problem(MWCDSP) classified as NP-complete problem. It is almost impossible to find a rule that directly finds the optimal solution of MWCDSP. The prerequisite for MWCDSP must meet the minimum sum of weights and the minimum number of connected nodes with it. This paper first obtains an MST that connecting n nodes with a minimum weighted sum. Next, in order to meet the condition of the minimum number of connected nodes, the nodes that dominating the terminal nodes with a degree of 2 or higher among the internal nodes of the MST were converted t...
1|2|3
Copyright © The Institute of Internet, Broadcasting and Communication. All rights reserved.
Address : 610 Dongbu Sunville, #99-6 GaRak-dong, SongPa-gu, Seoul, Korea | Tel : +82-2-407-7718, +82-70-7404-7718, Fax : + 82-2-407-7716 E-mail: iibc@iibc.kr