The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
하자 C 색상의 집합이 되고 Ω(c) 색상에 할당된 정수 비용이어야 합니다. c in C. 그래프의 가장자리 색상 G 가장자리 전체를 색칠하는 것입니다. G 인접한 두 가장자리가 서로 다른 색상으로 칠해지도록 C. 비용 Ω(f) 엣지 컬러링의 f of G 비용의 합은 Ω(f(e)) 색상 f(e) 모든 가장자리에 할당됨 e in G. 엣지 컬러링 f of G Ω(f)는 모든 가장자리 색상 중에서 최소입니다. G. 본 논문에서는 트리의 최적 가장자리 색칠을 찾는 문제를 보여줍니다. T 다음으로 구성된 새로운 이분 그래프에 대한 최소 가중치 완벽 매칭 문제로 다항식 시간을 간단하게 줄일 수 있습니다. T. 감소는 즉시 최적의 가장자리 색상을 찾는 효율적이고 간단한 알고리즘을 생성합니다. T 시간 O(n1.5Δ로그(nNω)), 어디 n 는 꼭지점의 개수입니다. T, Δ는 최대 차수입니다. T및 Nω 최대 절대 비용 | Ω(c)| 색상의 c in C. 그런 다음 결과가 다중 트리에 대해 확장될 수 있음을 보여줍니다.
연산, 비용 가장자리 착색, 멀티트리, 완벽한 매칭, 나무
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Takehiro ITO, Naoki SAKAMOTO, Xiao ZHOU, Takao NISHIZEKI, "Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 190-195, February 2011, doi: 10.1587/transinf.E94.D.190.
Abstract: 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 ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) 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(n1.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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.190/_p
부
@ARTICLE{e94-d_2_190,
author={Takehiro ITO, Naoki SAKAMOTO, Xiao ZHOU, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings},
year={2011},
volume={E94-D},
number={2},
pages={190-195},
abstract={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 ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) 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(n1.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.},
keywords={},
doi={10.1587/transinf.E94.D.190},
ISSN={1745-1361},
month={February},}
부
TY - JOUR
TI - Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings
T2 - IEICE TRANSACTIONS on Information
SP - 190
EP - 195
AU - Takehiro ITO
AU - Naoki SAKAMOTO
AU - Xiao ZHOU
AU - Takao NISHIZEKI
PY - 2011
DO - 10.1587/transinf.E94.D.190
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2011
AB - 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 ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) 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(n1.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.
ER -