서지주요정보
Path cover problems on bipartite interconnection networks = 이분 상호연결망에서의 경로 커버 문제
서명 / 저자 Path cover problems on bipartite interconnection networks = 이분 상호연결망에서의 경로 커버 문제 / Shin-Haeng Jo.
저자명 Jo, Shin-Haeng ; 조신행
발행사항 [대전 : 한국과학기술원, 2013].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8024891

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 13007

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

A \emph{paired many-to-many $k$-disjoint path cover} (\emph{$k$-DPC} for short) of a graph is a set of $k$ disjoint paths joining $k$ disjoint source-sink pairs that cover all the vertices of the graph. Extending the notion of DPC, we define a {\em paired many-to-many bipartite $k$-DPC} (\emph{$k$-BiDPC}) of a bipartite graph $G$ to be a set of $k$ disjoint paths joining $k$ distinct source-sink pairs that altogether cover the same number of vertices as the maximum number of vertices covered when the source-sink pairs are given in the complete bipartite, spanning supergraph of $G$. We consider the problem of finding paired many-to-many $2$-DPC and paired many-to-many $1$-BiDPC in an $m$-dimensional bipartite HL-graph and the problem of finding paired many-to-many $k$-BiDPC in an $m$-dimensional hypercube. It is proved that every $m$-dimensional bipartite HL-graph, under the condition that at most $m-3$ faulty edges removed, has a paired many-to-many $2$-DPC if the set of sources and sinks is balanced in the sense that it contains the same number of vertices from each part of the bipartition, where $m\geq 4$. Furthermore, every $m$-dimensional bipartite HL-graph, where $m\geq 4$, has a paired many-to-many 2-DPC in which the two paths have the same length if each source-sink pair is balanced in that source and sink do not have the same color. Using the $2$-DPC properties, it is proved that every $m$-dimensional bipartite HL-graph, under the condition that either at most $m-2$ faulty edges, or one faulty vertex and at most $m-3$ faulty edges removed has a paired many-to-many $1$-BiDPC, where $m\geq 3$. Using this result, we show that every $m$-dimensional hypercube, $Q_m$, under the condition that $f$ or less faulty elements (vertices and/or edges) are removed, has a paired many-to-many $k$-BiDPC joining $k$ distinct source-sink pairs for any $f$ and $k\geq 1$ subject to $f+2k\leq m$. This implies that $Q_m$ with $m-2$ or less faulty elements is strongly Hamiltonian-laceable.

그래프 $G$의 쌍형 다대다 $k$-서로소인 경로 커버는 $k$개의 시작점-끝점 쌍을 연결하며 그래프의 모든 정점을 지나는 $k$개의 서로소인 경로들의 집합이다. 이때 시작점과 끝점들의 집합은 서로소 임을 가정한다. 이를 이분그래프에 대해 확장하여, 이분 그래프 $G$의 쌍형 다대다 이분 $k$-서로소인 경로 커버를 $G$의 스패닝 슈퍼그래프인 이분 완전 그래프상에 이 시작점-끝점 쌍이 주어졌을 때, 이들을 연결하는 $k$개의 서로소인 경로들이 지날 수 있는 정점들의 최대 숫자와 동일한 수의 정점들을 지나는 시작점-끝점 쌍들을 연결하는 서로소인 경로 집합으로 정의한다. 최대 $m-3$개의 간선이 제거된 이분 유사 하이퍼큐브 그래프 부류의 그래프에서, 시작점들의 집합과 끝점들의 집합이 통틀어 각 이분파트에서 같은 숫자의 정점들을 가지면 시작점들과 끝점들을 잇는 쌍형 다대다 $2$-서로소인 경로 커버를 가짐이 증명되었다. 또한, 이분 유사 하이퍼큐브 그래프에서 두 시작점이 같은 이분파트 안에 존재하고, 두 끝점이 같은 이분파트 안에 존재하며, 시작점들과 끝점들이 포함된 이분파트들이 서로 다른 경우, 길이가 같은 두 경로로 구성된 $2$-서로소인 경로 커버가 존재함을 밝혔다. 이를 이용하여 최대 $m-2$개의 간선들, 혹은 1개의 정점과 최대 $m-3$개의 간선들이 제거된 이분 유사 하이퍼큐브 그래프 부류의 그래프가 임의의 시작점과 끝점 쌍을 연결하는 쌍형 다대다 이분 $1$-서로소인 경로 커버를 가짐이 증명되었다. 또한 이 성질을 이용하여 최대 $f$개의 고장 간선들과 정점들이 제거된 $m$차원 하이퍼큐브가 $f+2k\leq m$인 경우 임의의 시작점-끝점 쌍들을 잇는 쌍형 다대다 이분 $k$-서로소인 경로커버를 가짐을 증명하였다. 이는 최대 $m-2$개의 고장요소들이 제거된 $m$차원 하이퍼큐브가 강한 해밀턴 꿰기 성질을 가짐을 의미한다.

서지기타정보

서지기타정보
청구기호 {DCS 13007
형태사항 v, 53 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 조신행
지도교수의 영문표기 : Sung-Yong Shin
지도교수의 한글표기 : 신성용
공동지도교수의 영문표기 : Kyung-Yong Chwa
공동지도교수의 한글표기 : 좌경룡
학위논문 학위논문(박사) - 한국과학기술원 : 전산학과,
서지주기 References : p. 48-51
주제 disjoint path cover
hypercube
hypercube-like graphs
fault-tolerance
graph theory
서로 소인 경로 커버
하이퍼큐브
유사 하이퍼큐브 그래프
고장 감내
그래프 이론
QR CODE qr code