검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings 최소 비용으로 나무의 가장자리 색칠을 매칭으로 줄일 수 있습니다.

Takehiro ITO, Naoki SAKAMOTO, Xiao ZHOU, Takao NISHIZEKI

  • 조회수

    0

  • 이것을 인용

요약 :

하자 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, Δ는 최대 차수입니다. TNω 최대 절대 비용 | Ω(c)| 색상의 c in C. 그런 다음 결과가 다중 트리에 대해 확장될 수 있음을 보여줍니다.

발행
IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.190-195
발행일
2011/02/01
공개일
온라인 ISSN
1745-1361
DOI
10.1587/transinf.E94.D.190
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
범주

작성자

키워드