BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20151119T193000Z
DTEND:20151119T200000Z
LOCATION:18CD
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:ABSTRACT: With the increasing processing power of multicore computers, parallel graph search using shared memory machines has become increasingly feasible and important.  There has been a lot of progress on parallel breadth-first search, but less attention has been given to algorithms for unordered or loosely ordered traversals. We present a parallel algorithm for unordered depth-first-search on graphs.  We prove that the algorithm is work-efficient in a realistic, implementation-ready algorithmic model that includes important scheduling costs. This work-efficiency result applies to all graphs, including those with high diameter and high out-degree.  The key components of this result include a new data structure and a new amortization technique for controlling excess parallelism. We present an implementation and experiments that show that the algorithm performs well on a range of graphs and can lead to significant improvements over comparable algorithms.
SUMMARY:A Work-Efficient Algorithm for Parallel Unordered Depth-First Search
PRIORITY:3
END:VEVENT
END:VCALENDAR