BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20181221T160731Z
LOCATION:C140/142
DTSTART;TZID=America/Chicago:20181115T103000
DTEND;TZID=America/Chicago:20181115T110000
UID:submissions.supercomputing.org_SC18_sess208_pap115@linklings.com
SUMMARY:iSpan: Parallel Identification of Strongly Connected Components wi
 th Spanning Trees
DESCRIPTION:Paper\nApplications, Graph Algorithms, Security, Tech Program 
 Reg Pass\n\niSpan: Parallel Identification of Strongly Connected Component
 s with Spanning Trees\n\nJi, Liu, Huang\n\nDetecting strongly connected co
 mponents (SCCs) in a directed graph is crucial for understanding the struc
 ture of graphs. Most real-world graphs have one large SCC that contains th
 e majority of the vertices, and many small SCCs whose sizes are reversely 
 proportional to the frequency of their occurrence. For both types of SCCs,
  current approaches that rely on depth or breadth first search (DFS or BFS
 ) face the challenges of strict synchronization requirement and high compu
 tation cost. In this paper, we advocate a new paradigm of identifying SCCs
  with simple spanning trees, since SCC detection requires only the knowled
 ge of connectivity among the vertices. We have developed a prototype calle
 d iSpan which consists of parallel, relaxed synchronization construction o
 f spanning trees for detecting the large and small SCCs. The evaluations s
 how that iSpan is able to significantly outperform current state-of-the-ar
 t DFS and BFS- based methods by average 18× and 4×, respectively.
URL:https://sc18.supercomputing.org/presentation/?id=pap115&sess=sess208
END:VEVENT
END:VCALENDAR