KJCKorea
Journal Central

@article{ART002016382},
author={Sang-Un, Lee},
title={Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={7},
pages={41-47}

TY - JOUR
AU - Sang-Un, Lee
TI - Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 7
PB - The Korean Society Of Computer And Information
SP - 41
EP - 47
SN - 1598-849X
AB - The bandwidth minimization problem (BMP) has been classified as NP-complete because the polynomial time algorithm to find the optimal solution has been unknown yet. This paper suggests polynomial time heuristic algorithm is to find the solution of bandwidth minimization problem. To find the minimum bandwidth Φ*= minΦ(G),Φ(VG)= max{│f(vi)-f(vj):vi,vj∈E} for given graph m=│V│,n=│E│, the proposed algorithm sets the maximum degree vertex vi in graph G into global central point (GCP), and labels the median value⌈m+1/2⌉ between [1,m] range. The graph G is partitioned into subgroup, the maximum degree vertex in each subgroup is set to local central point (LCP), and we adjust the label of LCP per each subgroup as possible as minimum distance from GCP. The proposed algorithm requires O(mn) time complexity for label to all of vertices. For various twelve graph, the proposed algorithm can be obtains the same result as known optimal solution. For one graph, the proposed algorithm can be improve on known solution.
KW - Labeling;bandwidth;Maximum degree;Global central point;Local central point
DO -
UR -
ER -

Sang-Un, Lee. (2015). Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem. Journal of The Korea Society of Computer and Information, 20(7), 41-47.

Sang-Un, Lee. 2015, "Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem", Journal of The Korea Society of Computer and Information, vol.20, no.7 pp.41-47.

Sang-Un, Lee "Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem" Journal of The Korea Society of Computer and Information 20.7 pp.41-47 (2015) : 41.

Sang-Un, Lee. Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem. 2015; 20(7), 41-47.

Sang-Un, Lee. "Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem" Journal of The Korea Society of Computer and Information 20, no.7 (2015) : 41-47.

Sang-Un, Lee. Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem. Journal of The Korea Society of Computer and Information, 20(7), 41-47.

Sang-Un, Lee. Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem. Journal of The Korea Society of Computer and Information. 2015; 20(7) 41-47.

Sang-Un, Lee. Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem. 2015; 20(7), 41-47.

Sang-Un, Lee. "Maximum Degree Vertex Central Located Algorithm for Bandwidth Minimization Problem" Journal of The Korea Society of Computer and Information 20, no.7 (2015) : 41-47.