기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
2차원 토러스에서 다대다 서로소인 경로 커버
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 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.