版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Department of Computer Science University of South Carolina Columbia SC 29208 USA
出 版 物:《INFORMATION PROCESSING LETTERS》 (信息处理快报)
年 卷 期:1992年第41卷第3期
页 面:153-156页
核心收录:
学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:Slovenská Akadémia Vied SAV
主 题:PARALLEL ALGORITHMS GRAPH COLORING ROOTED TREES PLANAR GRAPHS OPTIMAL ALGORITHM
摘 要:An optimal O(DELTA-log n/log n) parallel algorithm for 3-coloring of rooted trees with maximum degree-DELTA that uses n log log n/log n processors on a CRCW PRAM is presented. This algorithm is used in the design of optimal parallel algorithms for 7-coloring of planar graphs, finding a maximal independent set and a maximal matching in planar graphs.