Vi beskriver effektiva deterministiska tekniker för att bryta symmetri parallellt. Dessa tekniker fungerar bra på rotade träd och grafer av konstant grad eller släkte. OUf primärteknik gör att vi kan 3-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 använder dessa tekniker för att konstruera snabba linjära processoralgoritmer för flera problem, inklusive problemet med (.6. + 1)-färgning konstant-gradig grafer och 5-färgning planar grafer. Vi visar också lägre gränser för 2-färgs riktade listor och för att hitta maximal oberoende uppsättningar i godtyckliga grafer.
Resultatet av REF sträcker sig också till 3-färgning av rotade träd, och 5-färgning av plana grafer.
Parallel Symmetry-Breaking in Sparse Graphs
{'venue': 'SIAM J. Discrete Math.', 'journal': 'SIAM J. Discrete Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}