Efficient Parallel Algorithms for (_+1)-coloring and Maximal Indepdendent Set Problems
dc.contributor.author | Goldberg, Andrew V. | en_US |
dc.contributor.author | Plotkin, Serge A. | en_US |
dc.date.accessioned | 2023-03-29T14:30:10Z | |
dc.date.available | 2023-03-29T14:30:10Z | |
dc.date.issued | 1987-01 | |
dc.identifier.uri | https://hdl.handle.net/1721.1/149128 | |
dc.description.abstract | We describe an efficient technique for breaking symmetry in paralle. The technique works especially well on rooted trees and on graphs with a small maximum degree. In particular, we can find a maximal independent set on a constant-degree graph in O(lg*n) time on an EREW PRAM using a linear number of processors. We show how to apply this technique to construct more efficient paralle algorithms for several problems, including coloring of planar graphs and (Δ+1)-coloring of constant-degree graphs. We also prove lower bounds for two related problems. | en_US |
dc.relation.ispartofseries | MIT-LCS-TM-320 | |
dc.title | Efficient Parallel Algorithms for (_+1)-coloring and Maximal Indepdendent Set Problems | en_US |