Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings

• ITO Takehiro

  Graduate School of Information Sciences, Tohoku University

• SAKAMOTO Naoki

  Graduate School of Information Sciences, Tohoku University

• ZHOU Xiao

  Graduate School of Information Sciences, Tohoku University

• NISHIZEKI Takao

  School of Science and Technology, Kwansei Gakuin University

抄録

Let C be a set of colors, and let ω(c) be an integer cost assigned to a color c in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors in C. The cost ω(ƒ) of an edge-coloring ƒ of G is the sum of costs ω(ƒ(e)) of colors ƒ(e) assigned to all edges e in G. An edge-coloring ƒ of G is optimal if ω(ƒ) is minimum among all edge-colorings of G. In this paper, we show that the problem of finding an optimal edge-coloring of a tree T can be simply reduced in polynomial time to the minimum weight perfect matching problem for a new bipartite graph constructed from T. The reduction immediately yields an efficient simple algorithm to find an optimal edge-coloring of T in time O(n^1.5Δlog (nN_ω)), where n is the number of vertices in T, Δ is the maximum degree of T, and N_ω is the maximum absolute cost |ω(c)| of colors c in C. We then show that our result can be extended for multitrees.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E94-D (2), 190-195, 2011

  一般社団法人 電子情報通信学会

キーワード

• algorithm
• cost edge-coloring
• multitree
• perfect matching
• tree

詳細情報

• CRID: 1390282679355083392
• NII論文ID: 130000453878
• DOI: 10.1587/transinf.e94.d.190
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E94.D/2/E94.D_2_190/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可