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:20210808T235336Z
LOCATION:Room A
DTSTART;TZID=America/Chicago:20210811T110000
DTEND;TZID=America/Chicago:20210811T111500
UID:icpp_ICPP 2021_sess112_pap255@linklings.com
SUMMARY:An Edge-Fencing Strategy for Optimizing SSSP Computations on Large
-Scale Graphs
DESCRIPTION:Conference Paper\n\nAn Edge-Fencing Strategy for Optimizing SS
SP Computations on Large-Scale Graphs\n\nYu, Wang, Luo\n\nThe Single-Sourc
e Shortest Path (SSSP) problem is to compute the shortest distances in a w
eighted graph from a source vertex to every other vertex. This paper focus
es on parallel efficiency and scalability of SSSP computations on large-sc
ale graphs. We propose an edge-fencing strategy to customize a SSSP algori
thm’s schedule for every SSSP computation, and devise a path-centric SSSP
algorithm with this strategy. This strategy aims at reducing both the rela
xed edges and relaxations repeated on each edge. It exploits a few fence v
alues to select the relaxed edges and schedule edge relaxations according
to lengths of the created paths. The path-centric algorithm works on a hie
rarchical graph model, and exploits the edge-fencing strategy to schedule
edge relaxations in parallel settings. The hierarchical graph model quanti
fies the length distribution of shortest paths in large-scale graphs, prov
ides appropriate fence values for every SSSP computation. The algorithm wa
s evaluated on a wide range of synthetic graphs and real-world graphs. The
experimental results suggest that our algorithm is efficient and scalable
for graphs with skewed degree distributions, and its performance is relat
ively insensitive to the hierarchical graph model’s accuracy.
END:VEVENT
END:VCALENDAR