호의 색칠문제의 해법 An Algorithm for the Edge Coloring Problem

Edge coloring problem is to find a minimum cardinality coloring of the edges of a graph so that any pair of edges incident to a common node do not have the same colors. Edge coloring problem is NP-hard, hence it is unlikely that there exists a polynomial time algorithm. We formulate the problem as a covering of the edges by matchings and find valid inequalities for the convex hull of feasible solutions. We show that adding the valid inequalities to the linear programming relaxation is enough to determine the minimum coloring number(chromatic index). We also propose a method to use the valid inequalities as cutting planes and do the branch and bound search implicitly. An example is given to show how the method works.
Publisher
대한산업공학회
Issue Date
1992-07
Language
KOR
Citation

대한산업공학회지, v.18, no.2, pp.43 - 49

ISSN
1225-0988
URI
http://hdl.handle.net/10203/65912
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 154
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0