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.
호색칠(Edge Coloring) 문제는 그래프의 각 호(edge)에 색칠을 하는데, 공통된 마디(node)에 인접한 호는 서로 다른 색을 갖도록 하면서 최소색의 수와 할당을 결정하는 문제이다. 이 문제는 일정계획이나 Electrical Network Design등에 나타난다. 호색칠문제는 호를 커버하는데 필요한 최소 갯수의 matching을 찾는 문제로 생각할 수 있으며 본 논문에서는 절단 평면을 사용하는 알고리듬으로 최적해를 구하였다. 절단 평면을 찾아내는 Separation Pocedure와 필요한 열(column)을 생성하는 Matching Procedure도 함께 소개되고 있다. 알고리듬을 세가지 random graph model에 적용시켜 본 결과, 대부분에서 이론상 가장 작은 갯수의 색으로 그래프를 칠할 수 있음을 알 수 있다.
