OPTIMAL PARALLEL 3-COLORING ALGORITHM FOR ROOTED TREES AND ITS APPLICATIONS

作     者：RAJCANI, P 

作者机构：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.