자료유형
등재정보
전체 선택해제
총 6건 검색
본문검색 결과만 보기
-
팬케익 그래프와 하프 팬케익 그래프에서 해밀턴 특성 분석
서정현(Jung-Hyun Seo), 이형옥(Hyeong Ok Lee) 인문사회과학기술융합학회 예술인문사회융합멀티미디어논문지 9 Pages
인문사회과학기술융합학회 예술인문사회융합멀티미디어논문지 2018, 제 8권 제 11호 86 913-921 (9 pages)
팬케익 문제는 크기가 모두 다른 다수의 팬케익을 접시에 쌓는 문제이다. 이때 크기가 작은 팬케익은 자신보다 큰 팬케익보다 위에 위치해야 한다. 팬케익 그래프는 n개의 크기가 서로 다른 팬케익 문제에서 출발했다. n-팬케익 그래프는 n!개의 노드를 가진다. 노드는 n개의 자연수로 된 순열로 이루어져 있다. 노드는 임의의 심볼에서부터 최상의 심볼까지 모두 뒤집는 것이 가능하다. 하프 팬케익 그래프와 팬케익 그래프는 스타그래프 부류의 연결망으로 노드수 n!을 갖는다. 하프 팬케익 그래프의 분지수는 팬케익 그래프의 분지수를... -
하프 버블정렬 그래프를 스타 그래프에 임베딩
서정현(Jung-Hyun Seo), 이형옥(HyeongOk Lee) 인문사회과학기술융합학회 예술인문사회융합멀티미디어논문지 9 Pages
인문사회과학기술융합학회 예술인문사회융합멀티미디어논문지 2018, 제 8권 제 9호 22 211-219 (9 pages)
상호연결망 분야에서 스타 그래프는 하이퍼큐브의 대안으로 발표되었다. 스타 그래프는 n!개의 노드를 가지며 노드 주소는 n개 자연수로 이루어진 순열로 표현된다. 스타 그래프는 노드는 첫 번째 심볼과 나머지 심볼 중 하나와 교환할 수 있다. 따라서 분지수는 n-1이다. 버블정렬 그래프는 스타 그래프 부류의 연결망으로 n!개의 노드를 가지며 노드는 이웃한 두 심볼을 교환할 수 있다. 따라서 분지수는 n-1이다. 하프 버블정렬 그래프는 버블정렬 그래프의 분지수 n-1을 절반으로 줄여 두 그래프가 같은 노드수 n!를 갖는 경우 망... -
하이퍼큐브의 망비용을 개선한 매트릭스 하이퍼큐브 설계 및 분석
서정현(Jung-Hyun Seo), 김종석(Jongseok Kim), 이형옥(HyeongOk Lee) 인문사회과학기술융합학회 예술인문사회융합멀티미디어논문지 9 Pages
인문사회과학기술융합학회 예술인문사회융합멀티미디어논문지 2018, 제 8권 제 7호 75 769-777 (9 pages)
상호연결망은 병렬 컴퓨터의 프로세서 연결 구조를 제공한다. 대표적인 상호연결망으로 토러스, 하이퍼큐브, 스타그래프가 있다. 하이퍼큐브는 재귀적 구조, 노드 대칭성, 간단한 라우팅 알고리즘 등 다양한 장점을 갖는 상호 연결망으로 가장 많이 상용화되고 있다. 본 논문에서는 하이퍼큐브의 망 비용을 개선하기 위해 분할정복 기법을 적용할 때 고려할 내용을 분석한다. 또한 연구 결과를 기반으로 분할정복 기법을 적용한 새로운 매트릭스 하이퍼큐브를 제안한다. 제안된 매트릭스 하이퍼큐브의 클러스터 성질을 분석하였다.... -
하프팬케익 그래프의 다양한 성질 분석
서정현, 이형옥, Seo. Jung-Hyun, Lee. HyeongOk 한국멀티미디어학회 멀티미디어학회논문지 8 Pages
한국멀티미디어학회 멀티미디어학회논문지 2014, Vol.17 No.6 725-732 (8 pages)
-
팬케익 그래프와 스타(Star) 그래프, 매크로-스타(Macro-star) 그래프간의 임베딩 방법
최은복, 이형옥 한국멀티미디어학회 멀티미디어학회논문지 9 Pages
한국멀티미디어학회 멀티미디어학회논문지 2003, Vol.6 No.3 556-564 (9 pages)
스타 그래프와 팬케익 그래프는 하이퍼큐브가 갖는 좋은 성질을 가지면서 하이퍼큐브보다 망 비용이 적은 값을 갖는 상호연결망이다. 매크로-스타 그래프는 스타 그래프를 기본 모듈로 하면서 노드 대칭성, 최대고장허용도, 계층적 분할 성질을 가지면서 스타 그래프보다 망 비용이 개선된 상호연결망이다. 본 논문에서는 그래프의 에지 정의를 이용하여 스타 그래프, 팬케익 그래프, 매크로-스타 그래프 사이의 임베딩 방법을 제시한다. 스타 그래프 $S_n$은 팬케익 그래프 $P_n$에 연장율 4에 임베딩 가능하고, 매크로-스타 MS(2,n)은... -
스타 그래프와 팬케익, 버블정렬 그래프 사이의 임베딩 알고리즘
김종석, 이형옥, 김성원, Kim. Jong-Seok, Lee. Hyeong-Ok, Kim. Sung-Won 한국컴퓨터교육학회 컴퓨터교육학회논문지 12 Pages
한국컴퓨터교육학회 컴퓨터교육학회논문지 2010, Vol.13 No.5 91-102 (12 pages)
스타 그래프는 노드 대칭성, 최대 고장 허용도, 계층적 분할 성질을 갖고, 하이퍼큐브보다 망 비용이 개선된 널리 알려진 상호 연결망이다. 본 연구에서는 스타 그래프와 그의 변형된 그래프들 상호 간의 임베딩 방법을 제안한다. 버블정렬 그래프가 팬케익 그래프와 스타 그래프에 각각 연장율 3, 확장율 1로 임베딩 가능함을 보이고, 팬케익 그래프가 버블정렬그래프에 임베딩 하는 연장율 비용이 O($n^2$)임을 보인다. 그리고 스타 그래프가 팬케익 그래프에 연장율 4, 확장율 1로 임베딩 가능함을 보인다. 또한 스타그래프를 버블정렬...
