Vi beskriver effektiva deterministiska tekniker för att bryta symmetri parallellt. Teknikerna fungerar bra på rotade träd och grafer av konstant grad eller släkte. Vår primära teknik gör att vi kan t-färga ett rotat träd i O (lg'n) tid på en EREW PRAM med hjälp av ett linjärt antal processorer. Vi tillämpar dessa tekniker för att konstruera snabba linjära processoralgoritmer för flera problem, inklusive (A + I)-färgning konstant-graders grafer, 5-färgning planar grafer, och hitta djup-första-sök träd i plana grafer. Vi visar också lägre gränser för a-färga riktade listor och för att hitta maximal oberoende uppsättningar i godtyckliga grafer.
Goldberg m.fl. REF beskriver en algoritm för att hitta en girig färgning av O(1)-graders grafer i O(lg n)-tid i EREW PRAM-modellen med hjälp av ett linjärt antal processorer.
Parallel symmetry-breaking in sparse graphs
{'venue': "STOC '87", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}