서지주요정보
Finding a plane subgraph with a certain property in ordered bipartite graphs = 순서화된 이분 그래프에서 평면 부 그래프를 찾는 문제들에 관한 연구
서명 / 저자 Finding a plane subgraph with a certain property in ordered bipartite graphs = 순서화된 이분 그래프에서 평면 부 그래프를 찾는 문제들에 관한 연구 / Se-Chang Son.
저자명 Son, Se-Chang ; 손세창
발행사항 [대전 : 한국과학기술원, 1990].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8001271

소장위치/청구기호

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

MCS 9016

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This thesis introduces a new graph-an ordered bipartite graph and considers several problems on the ordered bipartite graph. An ordered bipartite graph is defined as a bipartite graph which has a specific geometric property such that the edges connecting two vertices are line segments, and the vertices are lying on two parallel lines and the vertices on each parallel line are ordered. This thesis presents simple and efficient algorithms for the problems to find certain subgraphs, of a given ordered bipartite graph, which satisfy a specified property and of which no two edges intersect each other. Using the algorithm for finding a maximum independent set of a permutation graph, O(|E(G)|log|V(G)|) algorithms for the minimum plane tree cover and the maximum plane matching problems were presented, where |E(G)| and |V (G)| are the cardinalities of the edge set and the vertex set, respectively. For the minimum plane spanning tree, the longest plane path, and the plane Steiner tree problems, linear time algorithms were developed by using the dynamic programming. The minimum plane tree cover and the minimum plane spanning tree problems have the applications in PCB routing and the maximum plane matching problem in VLSI routing.

순서화된 이분그래프(ordered bipartite graph)는 정점들이 두개의 평행선상에 있고 각 선상의 정점끼리 순서가 정해진 이분그래프이다. 본 논문에서는 주어진 순서화된 이분그래프에 대해 특정한 성질을 만족하면서 서로 교차하는 에지를 갖지 않는 부그래프를 찾는 문제들을 고려하였다. 최소 plane tree cover와 최대 plane matching 문제에 대해서는 O(| E(G)|log|V(G)| 알고리즘을 제안하였고 최소 plane spanning tree, 최장 plane path, plane Steiner tree 문제들에 대해서는 각각 선형시간의 알고리즘을 제안하였다.

서지기타정보

서지기타정보
청구기호 {MCS 9016
형태사항 [ii], 32, [4] p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 손세창
지도교수의 영문표기 : Kyung-Yong Chwa
지도교수의 한글표기 : 좌경룡
학위논문 학위논문(석사) - 한국과학기술원 : 전산학과,
서지주기 Reference : p. 34-36
주제 Algorithms.
그래프 이론. --과학기술용어시소러스
평면 그래프. --과학기술용어시소러스
알고리즘. --과학기술용어시소러스
Graph theory.
QR CODE qr code