BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20210402T160105Z
LOCATION:Track 3
DTSTART;TZID=America/New_York:20201119T150000
DTEND;TZID=America/New_York:20201119T153000
UID:submissions.supercomputing.org_SC20_sess160_pap410@linklings.com
SUMMARY:High-Performance Parallel Graph Coloring with Strong Guarantees on
  Work, Depth and Quality
DESCRIPTION:Paper\n\nHigh-Performance Parallel Graph Coloring with Strong 
 Guarantees on Work, Depth and Quality\n\nBesta, Carigiet, Janda, Vonarburg
 -Shmaria, Gianinazzi...\n\nWe develop the first parallel graph coloring he
 uristic with strong theoretical guarantees on work and depth and coloring 
 quality. The key idea is to design a relaxation of the vertex degeneracy o
 rder, a well-known graph theory concept, and to color vertices in the orde
 r dictated by this relaxation. This introduces a tunable amount of paralle
 lism into the degeneracy ordering that is otherwise hard to parallelize. T
 his simple idea enables significant benefits in several key aspects of gra
 ph coloring. For example, one of our algorithms ensures polylogarithmic de
 pth and a bound on the number of used colors that is superior to all other
  parallelizable schemes, while maintaining work efficiency. In addition to
  provable guarantees, the developed algorithms have competitive runtimes f
 or several real-world graphs, while almost always providing superior color
 ing quality. Our degeneracy ordering relaxation is of separate interest fo
 r algorithms outside the context of coloring.\n\nTag: Graph Algorithms, Sc
 alable Computing\n\nRegistration Category: Tech Program Reg Pass
END:VEVENT
END:VCALENDAR