BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20260224T163000
DTEND;TZID=Asia/Seoul:20260224T173000
DTSTAMP:20260416T034930
CREATED:20251119T205949Z
LAST-MODIFIED:20260202T004550Z
UID:11865-1771950600-1771954200@dimag.ibs.re.kr
SUMMARY:Marek Sokołowski\, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
DESCRIPTION:In this talk\, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly\, we prove that directed SSSP can be solved within $\widetilde{O}(m+n^{2-\varepsilon})$ work and $\widetilde{O}(n^{1-\varepsilon})$ depth for some positive $\varepsilon>0$. For dense graphs with non-negative real weights\, this yields the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Moreover\, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights. \nThis is a joint work with Adam Karczmarz and Wojciech Nadara.
URL:https://dimag.ibs.re.kr/event/2026-02-24/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR