Negative-Weight Single-Source Shortest Paths in Near-linear Time
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Accepteret manuskript, 544 KB, PDF-dokument
We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog(8)(n) logW) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are (O) over tilde ((m + n(1.5)) logW) [BLNPSSSW FOCS'20] and m(4/3+o(1)) logW [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic (O) over tilde (m root n logW) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
Originalsprog | Engelsk |
---|---|
Titel | 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) |
Forlag | IEEE |
Publikationsdato | 2022 |
Sider | 600-611 |
ISBN (Elektronisk) | 978-1-6654-5519-0 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) - Denver, Colombia Varighed: 31 okt. 2022 → 3 nov. 2022 |
Konference
Konference | 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS) |
---|---|
Land | Colombia |
By | Denver |
Periode | 31/10/2022 → 03/11/2022 |
Navn | Annual IEEE Symposium on Foundations of Computer Science |
---|---|
ISSN | 0272-5428 |
ID: 337602711