정보과학회논문지 (Journal of KIISE)
Current Result Document : 10 / 378
이전건
다음건 
| 한글제목(Korean Title) |
에지에 고장이 있는 이분그래프가 아닌 k-ary n-cube의 일대일 서로소인 경로커버 |
| 영문제목(English Title) |
One-to-One Disjoint Cover of Non-bipartite k-ary n-cube with Faulty Edges |
| 저자(Author) |
김희철
조상영
신찬수
Hee-Chul Kim
Sang-Young Cho
Chan-Su Shin
|
| 원문수록처(Citation) |
VOL 48 NO. 12 PP. 1251 ~ 1273 (2021. 12) |
한글내용
(Korean Abstract) |
그래프 G에서 소스 정점 s, 싱크 정점 t를 잇는 일대일 서로소인 r-경로커버는 s 와 t 를 잇는 r 개의 경로들로서 이들 경로가 G의 모든 정점들을 지나면서 s 와 t 를 제외한 다른 정점은 중복해서 지나지 않는 것이다. 이 논문에서는 상호연결망으로 잘 알려진 k-ary n-cube Q에서 에지에 고장이 있는 경우에 일대일 서로소인 경로커버 문제를 고려한다. n ≥ 3이고, k 가 3 이상 홀수(이분 그래프가 아닌)인 Q 에서 고장인 에지들 개수 f가 2n-3 이하일 때, f+r ≤ 2n 인 모든 r 에 대하여 임의의 두 정점을 잇는 일대일 서로소인 r-경로커버가 존재함을 보인다. f+r 에 대한 상한 2n 은 최선의 상한이다. |
영문내용
(English Abstract) |
Given a graph G, a source s, and a sink t, one-to-one r-disjoint path cover joining s and t is a set of r internally vertex disjoint paths joining s and t which cover all vertices in G. In this paper, we consider one-to-one disjoint path cover problem in the k-ary n-cube with faulty edges which is one of the well-known interconnection networks. It is shown that in non-bipartite k-ary n-cube Q with n ≥ 2, k ≥ 3, and f faulty edges where f ≤ 2n-3, there is one-to-one r-disjoint path cover joining any two vertices for any r with f r ≤ 2n. The upper bound, 2n, on f r is the best possible. |
| 키워드(Keyword) |
일대일 서로소인 경로커버
상호연결망
k-ary n-cubes
고장 감내
one-to-one disjoint path cover
interconnection networks
k-ary n-cubes
fault tolerance
|
| 파일첨부 |
PDF 다운로드
|
