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.

- Advisors
- Chwa, Kyung-Yong
*researcher*; 좌경룡*researcher*

- Description
- 한국과학기술원 : 전산학과,

- Publisher
- 한국과학기술원

- Issue Date
- 1990

- Identifier
- 67270/325007 / 000881222

- Language
- eng

- Description
학위논문(석사) - 한국과학기술원 : 전산학과, 1990.2, [ [ii], 32, [4] p. ]

- Appears in Collection
- CS-Theses_Master(석사논문)

- Files in This Item
- There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.