Parallel edge coloring of a tree on a mesh connected computer

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

    Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
    Title of host publicationTheoretical Computer Science
    Subtitle of host publicationExploring New Frontiers of Theoretical Informatics - International Conference IFIP TCS 2000, Proceedings
    EditorsJan van Leeuwen, Osamu Watanabe, Masami Hagiya, Peter D. Mosses, Takayasu Ito
    PublisherSpringer Verlag
    Pages76-83
    Number of pages8
    ISBN (Print)3540678239, 9783540678236
    DOIs
    Publication statusPublished - 2000
    Event 1st IFIP International Conference on Theoretical Computer Science, TCS 2000 - Sendai, Japan
    Duration: 2000 Aug 172000 Aug 19

    Publication series

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

    Conference

    Conference 1st IFIP International Conference on Theoretical Computer Science, TCS 2000
    Country/TerritoryJapan
    CitySendai
    Period00/8/1700/8/19

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'Parallel edge coloring of a tree on a mesh connected computer'. Together they form a unique fingerprint.

    Cite this