Earticle

초록

영어

This paper suggests polynomial time algorithm for cutwidth minimization problem that classified as NP-complete because the polynomial time algorithm to find the optimal solution has been unknown yet. To find the minimum cutwidth CWf(G) = max v∈V CWf(v) for given graph G=(V,E), m=|V|, n=|E|, the proposed algorithm divides neighborhood N G[vi] of the maximum degree vertex vi in graph G into left and right and decides the vertical cut plane with minimum number of edges pass through the vertex vi firstly. Then, we split the left and right N G[vi] into horizontal sections with minimum pass through edges. Secondly, the inner-section vertices are connected into line graph and the inter-section lines are connected by one line layout. Finally, we perform the optimization process in order to obtain the minimum cutwidth using vertex moving method. Though the proposed algorithm requires O(n2) time complexity, that can be obtains the optimal solutions for all of various experimental data

한국어

본 논문은 NP-완전으로 최적 해를 구하는 다항시간 알고리즘이 알려져 있지 않은 절단 폭 최소화 문제에 대해 다항시간 알고리즘을 제안하였다. 주어진 그래프 G=(V,E), m=|V|, n=|E|에 대한 최소 절단 폭 CWf(G) = max v∈V CWf(v)를 찾기 위해 제안된 알고리즘은 첫 번째로, 최대차수 정점 vi를 기준으로 N G[vi] 정점들을 vi 를 통과하 는 간선수가 최소가 되도록 양분하는 열 절단면을 찾고, 좌ㆍ우의 N G[vi]들 간의 통과 간선수가 최소가 되는 행 절단면으 로 분할하였다. 두 번째로, 각 부 그래프 내부의 정점들을 선형으로 연결하고, 부 그래프들 간 간선을 연결하여 하나의 선형 배열을 만들었다. 마지막으로, 정점을 이동시켜 최소 절단폭을 갖는 최적화 과정을 수행하였다. 다양한 그래프들을 대상으로 실험한 결과, 수행 복잡도가 O(n2)인 제안된 알고리즘을 모든 데이터들에 대해 최적 해를 찾을 수 있었다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 절단 폭 최소화 문제 고찰
Ⅲ. 최대차수 정점 분할 알고리즘
Ⅳ. 알고리즘 적용 및 결과 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380