Finding a plane subgraph with a certain property in ordered bipartite graphs = 순서화된 이분 그래프에서 평면 부 그래프를 찾는 문제들에 관한 연구

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 285
  • Download : 0
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-Yongresearcher좌경룡researcher
Description
한국과학기술원 : 전산학과,
Publisher
한국과학기술원
Issue Date
1990
Identifier
67270/325007 / 000881222
Language
eng
Description

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

URI
http://hdl.handle.net/10203/33887
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=67270&flag=dissertation
Appears in Collection
CS-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0