- 재귀원형군과 토러스에서 쌍형 다대다 서로소인 경로 커버
- ㆍ 저자명
- 김유상,박정흠,Kim. Eu-Sang,Park. Jung-Heum
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2009년|36권 1호|pp.40-51 (12 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
그래프 G의 쌍형 다대다 k-서로소인 경로 커버(쌍형 k-DPC)는 k개의 서로 다른 소스-싱크 쌍을 연결하며 그래프에 있는 모든 정점을 지나는 k개의 서로소인 경로 집합이다. 이 논문에서는 재귀원형군 G($cd^m$,d), $d{geq}3$과 토러스에서 서로소인 경로 커버를 고려하여, 이분 그래프가 아니고 분지수가 $delta$인 재귀원형군과 토러스는 고장 요소(정점이나 에지)가 f개 이하일 때 $f+2k{leq}{delta}-1$을 만족하는 임의의 f, $k{geq}1$에 대하여 쌍형 k-DPC를 가짐을 보인다.
A paired many-to-many k-disjoint path cover (paired k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. In this paper, we investigate disjoint path covers in recursive circulants G($cd^m$,d) with $d{geq}3$ and tori, and show that provided the number of faulty elements (vertices and/or edges) is f or less, every nonbipartite recursive circulant and torus of degree $delta$ has a paired k-DPC for any f and $k{geq}1$ with $f+2k{leq}{delta}-1$.