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:20260522T150117Z
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:Yuede Ji (George Washington University); Hang Liu (University 
 of Massachusetts, Lowell); and H. Howie Huang (George Washington Universit
 y)\n\nDetecting strongly connected components (SCCs) in a directed graph i
 s crucial for understanding the structure of graphs. Most real-world graph
 s have one large SCC that contains the majority of the vertices, and many 
 small SCCs whose sizes are reversely proportional to the frequency of thei
 r occurrence. For both types of SCCs, current approaches that rely on dept
 h or breadth first search (DFS or BFS) face the challenges of strict synch
 ronization requirement and high computation cost. In this paper, we advoca
 te a new paradigm of identifying SCCs with simple spanning trees, since SC
 C detection requires only the knowledge of connectivity among the vertices
 . We have developed a prototype called iSpan which consists of parallel, r
 elaxed synchronization construction of spanning trees for detecting the la
 rge and small SCCs. The evaluations show that iSpan is able to significant
 ly outperform current state-of-the-art DFS and BFS- based methods by avera
 ge 18× and 4×, respectively.\n\nTag: Applications, Graph Algorithms, Secur
 ity\n\nRegistration Category: Tech Program Reg Pass\n\nSession Chair: Most
 ofa Patwary (NVIDIA Corporation)\n\n
END:VEVENT
END:VCALENDAR