- 2차원 토러스에서 다대다 서로소인 경로 커버
- ㆍ 저자명
- 박정흠,Park. Jung-Heum
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2011년|38권 1호|pp.42-48 (7 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
그래프 G의 쌍형 다대다 k-서로소인 경로 커버 (k-DPC)는 k개의 서로 다른 소스 정점과 싱크 정점 쌍을 연결하며 그래프에 있는 모든 정점을 지나는 k개의 서로소인 경로 집합을 말한다. 2차원 $m{ imes}n$ 토러스는 길이가 각각 m과 n인 두 사이클 $C_m$과 $C_n$의 곱으로 정의되는 그래프이다. 이 논문에서는 $m{ imes}n$ 토러스($m{geq}3$, 홀수 $n{geq}3$)는 임의의 두 소스-싱크 쌍을 잇는 쌍형 다대다 2-DPC를 가짐을 보인다. 이 결과는 $m{ imes}n$ 토러스가 항상 3-DPC를 가지지는 않는다는 점과 정점이나 에지에 고장이 하나 있더라도 항상 2-DPC를 가지지는 않는다는 점에서 최적이다.
A paired many-to-many k-disjoint path cover (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. A two-dimensional $m{ imes}n$ torus is a graph defined as a product of two cycles $C_m$ and $C_n$ of length m and n, respectively. In this paper, we show that an $m{ imes}n$ torus with $m{geq}3$ and odd $n{geq}3$ has a 2-DPC joining any two source-sink pairs of vertices. This result is optimal in a sense that an $m{ imes}n$ torus does not always have a 3-DPC and that the graph with one faulty vertex or edge does not always have a 2-DPC.