Parallel edge coloring of a tree on a mesh connected computer

Chang Sung Jeong; Sung Up Cho; Sun Chul Whang; Mi Young Choi

doi:10.1007/3-540-44929-9_6

Parallel edge coloring of a tree on a mesh connected computer

Chang Sung Jeong, Sung Up Cho, Sun Chul Whang, Mi Young Choi

School of Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

An edge coloring is an assignment of colors to the edges of a graph so that no two edges with a common vertex have the same color. We show that, given an undirected tree T with n vertices, a minimum edge coloring of T can be determined in O(p n) time on a p(n) p (n) mesh-connected computer(MCC) by a novel technique which decomposes the tree into disjoint chains and then assigns the edge colors in each chain properly. The time complexity is optimal on MCC within constant factor.

Original language	English
Title of host publication	Theoretical Computer Science
Subtitle of host publication	Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings
Editors	Jan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito
Publisher	Springer Verlag
Pages	76-83
Number of pages	8
ISBN (Print)	3540678239, 9783540678236
DOIs	https://doi.org/10.1007/3-540-44929-9_6
Publication status	Published - 2000
Event	1st IFIP International Conference on Theoretical Computer Science, TCS 2000 - Sendai, Japan Duration: 2000 Aug 17 → 2000 Aug 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1872 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st IFIP International Conference on Theoretical Computer Science, TCS 2000
Country/Territory	Japan
City	Sendai
Period	00/8/17 → 00/8/19

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-44929-9_6

Cite this

Jeong, C. S., Cho, S. U., Whang, S. C., & Choi, M. Y. (2000). Parallel edge coloring of a tree on a mesh connected computer. In J. van Leeuwen, O. Watanabe, M. Hagiya, P. D. Mosses, & T. Ito (Eds.), Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings (pp. 76-83). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1872 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-44929-9_6

Parallel edge coloring of a tree on a mesh connected computer. / Jeong, Chang Sung; Cho, Sung Up; Whang, Sun Chul et al.
Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings. ed. / Jan van Leeuwen; Osamu Watanabe; Masami Hagiya; Peter D. Mosses; Takayasu Ito. Springer Verlag, 2000. p. 76-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1872 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Jeong, CS, Cho, SU, Whang, SC & Choi, MY 2000, Parallel edge coloring of a tree on a mesh connected computer. in J van Leeuwen, O Watanabe, M Hagiya, PD Mosses & T Ito (eds), Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1872 LNCS, Springer Verlag, pp. 76-83, 1st IFIP International Conference on Theoretical Computer Science, TCS 2000, Sendai, Japan, 00/8/17. https://doi.org/10.1007/3-540-44929-9_6

Jeong CS, Cho SU, Whang SC, Choi MY. Parallel edge coloring of a tree on a mesh connected computer. In van Leeuwen J, Watanabe O, Hagiya M, Mosses PD, Ito T, editors, Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings. Springer Verlag. 2000. p. 76-83. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44929-9_6

Jeong, Chang Sung ; Cho, Sung Up ; Whang, Sun Chul et al. / Parallel edge coloring of a tree on a mesh connected computer. Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings. editor / Jan van Leeuwen ; Osamu Watanabe ; Masami Hagiya ; Peter D. Mosses ; Takayasu Ito. Springer Verlag, 2000. pp. 76-83 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f49c518aa70540ea9968b35dc2b58539,

title = "Parallel edge coloring of a tree on a mesh connected computer",

abstract = "An edge coloring is an assignment of colors to the edges of a graph so that no two edges with a common vertex have the same color. We show that, given an undirected tree T with n vertices, a minimum edge coloring of T can be determined in O(p n) time on a p(n) p (n) mesh-connected computer(MCC) by a novel technique which decomposes the tree into disjoint chains and then assigns the edge colors in each chain properly. The time complexity is optimal on MCC within constant factor.",

author = "Jeong, {Chang Sung} and Cho, {Sung Up} and Whang, {Sun Chul} and Choi, {Mi Young}",

year = "2000",

doi = "10.1007/3-540-44929-9_6",

language = "English",

isbn = "3540678239",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "76--83",

editor = "{van Leeuwen}, Jan and Osamu Watanabe and Masami Hagiya and Mosses, {Peter D.} and Takayasu Ito",

booktitle = "Theoretical Computer Science",

note = " 1st IFIP International Conference on Theoretical Computer Science, TCS 2000 ; Conference date: 17-08-2000 Through 19-08-2000",

}

TY - GEN

T1 - Parallel edge coloring of a tree on a mesh connected computer

AU - Jeong, Chang Sung

AU - Cho, Sung Up

AU - Whang, Sun Chul

AU - Choi, Mi Young

PY - 2000

Y1 - 2000

N2 - An edge coloring is an assignment of colors to the edges of a graph so that no two edges with a common vertex have the same color. We show that, given an undirected tree T with n vertices, a minimum edge coloring of T can be determined in O(p n) time on a p(n) p (n) mesh-connected computer(MCC) by a novel technique which decomposes the tree into disjoint chains and then assigns the edge colors in each chain properly. The time complexity is optimal on MCC within constant factor.

AB - An edge coloring is an assignment of colors to the edges of a graph so that no two edges with a common vertex have the same color. We show that, given an undirected tree T with n vertices, a minimum edge coloring of T can be determined in O(p n) time on a p(n) p (n) mesh-connected computer(MCC) by a novel technique which decomposes the tree into disjoint chains and then assigns the edge colors in each chain properly. The time complexity is optimal on MCC within constant factor.

UR - http://www.scopus.com/inward/record.url?scp=84879070793&partnerID=8YFLogxK

U2 - 10.1007/3-540-44929-9_6

DO - 10.1007/3-540-44929-9_6

M3 - Conference contribution

AN - SCOPUS:84879070793

SN - 3540678239

SN - 9783540678236

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 76

EP - 83

BT - Theoretical Computer Science

A2 - van Leeuwen, Jan

A2 - Watanabe, Osamu

A2 - Hagiya, Masami

A2 - Mosses, Peter D.

A2 - Ito, Takayasu

PB - Springer Verlag

T2 - 1st IFIP International Conference on Theoretical Computer Science, TCS 2000

Y2 - 17 August 2000 through 19 August 2000

ER -

Parallel edge coloring of a tree on a mesh connected computer

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this