Loading...
2005
메쉬 연결망의 강한 해밀톤 laceability
Strongly Hamiltonian Laceability of Mesh Networks
한국정보과학회
임형석 외 1명
논문정보
- Publisher
- 정보과학회논문지 : 시스템 및 이론
- Issue Date
- 2005-08-31
- Keywords
- -
- Citation
- -
- Source
- -
- Journal Title
- -
- Volume
- 32
- Number
- 8
- Start Page
- 393
- End Page
- 398
- DOI
- ISSN
- 1229683X
Abstract
연결망에서 해밀톤 경로는 선형 배열 구현이나 멀티캐스팅과 같은 여러 응용에서 활용된다. 본 논문에서는 여러 병렬 시스템의 상호연결망으로 사용되는 메쉬 연결망의 해밀톤 성질에 대해 고려한다. 연결망이 강한 해밀톤 laceable이면 그 연결망은 임의의 두 노드를 잇는 가능한 가장 긴 길이의 경로를 지닌다. 2차원 메쉬 은 노드의 수가 짝수이면 일 때, 노드의 수가 홀수이면 일 때 강한 해밀톤 laceable 그래프임을 보인다. 메쉬는 토러스, -ary -큐브, 하이퍼큐브, 재귀원형군과 같은 여러 상호 연결망들의 스패닝 부 그래프이므로 본 논문의 결과는 이들 연결망들의 고장 해밀톤 성질을 밝히는데 활용될 수 있다.
- 전남대학교
- KCI
- 정보과학회논문지 : 시스템 및 이론
저자 정보
| 이름 | 소속 |
|---|---|
| 임형석 | 소프트웨어공학과 |