Parallel symmetry-breaking in sparse graphs
Parallel symmetry-breaking in sparse graphs
复制标题
稀疏图中的并行对称性破缺
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
Gregory E. Shannon
中科院分区：
文献类型：
--
作者：
Andrew V. Goldberg;Serge A. Plotkin;Gregory E. Shannon
我们描述了并联破坏对称性的有效确定性技术。这些技术在根树和恒定程度或属的图上很好地工作。我们的主要技术使我们可以使用线性数量的处理器在EREW PRAM上进行3色树的3色。我们将这些技术应用于为几个问题构建快速线性处理器算法，包括（＆dgr; + 1） - 颜色的恒定度图，5色平面图以及在平面图中找到深度优先搜索树。我们还证明了2个彩色的有向列表和在任意图中找到最大独立集的下限。
We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in &Ogr;(lg*n) time on an EREW PRAM using a linear number of processors. We apply these techniques to construct fast linear processor algorithms for several problems, including (&Dgr; + 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees in planar graphs. We also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs.