DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Park, Sung-Soo | - |
dc.contributor.advisor | 박성수 | - |
dc.contributor.author | Choi, Jeong-Soon | - |
dc.contributor.author | 최정순 | - |
dc.date.accessioned | 2011-12-14T04:18:06Z | - |
dc.date.available | 2011-12-14T04:18:06Z | - |
dc.date.issued | 1993 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=68817&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/41405 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 산업공학과, 1993.2, [ [iii], 32 p. ] | - |
dc.description.abstract | Edge coloring problem is to find a coloring of the edges of a given graph with minimum number of colors so that any pair of edges that are incident to a common node have different colors. This is one of the combinatorial optimization problem on graphs and related to such diverse fields as several scheduling problems in operations research, electrical network analysis and statistics. We consider the edge coloring problem on a simple graph as the integer program of covering edges by matchings. In this paper we describe an implementation of algorithm for it. The algorithm uses a polyhedral cutting plane. And linear programming based weighted matching procedure is introduced for generating columns. Moreover the algorithm adopts an efficient branching scheme that makes the graph smaller by deleting some matchings. The implementation of the algorithm is described in details and computational results are given. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.title | (A) polyhedral cutting plane algorithm for the edge coloring problem | - |
dc.title.alternative | 호색칠문제의 절단평면 알고리듬 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 68817/325007 | - |
dc.description.department | 한국과학기술원 : 산업공학과, | - |
dc.identifier.uid | 000911608 | - |
dc.contributor.localauthor | Park, Sung-Soo | - |
dc.contributor.localauthor | 박성수 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.