BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Denver
X-LIC-LOCATION:America/Denver
BEGIN:DAYLIGHT
TZOFFSETFROM:-0700
TZOFFSETTO:-0600
TZNAME:MDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0600
TZOFFSETTO:-0700
TZNAME:MST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260422T000712Z
LOCATION:401-402
DTSTART;TZID=America/Denver:20231114T113000
DTEND;TZID=America/Denver:20231114T120000
UID:submissions.supercomputing.org_SC23_sess155_pap619@linklings.com
SUMMARY:PeeK: A Prune-Centric Approach for K Shortest Path Computation
DESCRIPTION:Wang Feng (University of North Texas), Shiyang Chen and Hang L
 iu (Rutgers University), and Yuede Ji (University of North Texas)\n\nThe 𝐾
  shortest path (KSP) algorithm, which finds the top 𝐾 shortest simple path
 s from a given source to a target vertex, has a wide range of real-world a
 pplications. While the top 𝐾 shortest simple paths offer invaluable insigh
 ts, computing them is time-consuming. In this work, we observe existing wo
 rks search 𝐾 shortest paths from the original graph, while the top 𝐾 short
 est paths only cover a meager portion of the original graph. This paper de
 vises PeeK. It first applies 𝐾 upper bound pruning to prune the vertices a
 nd edges that will not appear in any of the 𝐾 shortest paths. Second, PeeK
  adaptively compacts the graph that, not only removes the deleted vertices
  or edges but also efficiently computes the downstream task. We compare Pe
 eK with five algorithms. For parallel computation with 32 threads, PeeK ac
 hieves 5.1x and 28.8x speedup over the state-of-the-art for 𝐾 = 8, 128, re
 spectively.\n\nTag: Accelerators, Algorithms, Graph Algorithms and Framewo
 rks\n\nRegistration Category: Tech Program Reg Pass\n\nReproducibility Bad
 ges: Artifact Available, Artifact Functional, Results Reproduced\n\nSessio
 n Chair: Marco Minutoli (Advanced Micro Devices)\n\n
END:VEVENT
END:VCALENDAR