All-pairs nearly 2-approximate shortest paths in $O(n^2 \mathrm polylog n)$ time

Surender Baswana, Vishrut Goyal, Sandeep Sen, Volker Diekert, Bruno Durand

Type: Article

Publication Date: 2005-01-01

Citations: 3

Locations

Untitled Event - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrierand Derandomization	2016	Monika Henzinger Sebastian Krinninger Danupon Nanongkai
+ PDF Chat	Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization	2015	Monika Henzinger Sebastian Krinninger Danupon Nanongkai
+ PDF Chat	Efficient parameterized algorithms for computing all-pairs shortest paths	2023	Stefan Kratsch Florian Nelles
+ PDF Chat	Fast 2-Approximate All-Pairs Shortest Paths	2024	Michal Dory Sebastian Förster Yael Kirkpatrick Yasamin Nazari Virginia Vassilevska Williams Tijn de Vos
+	Fast 2-Approximate All-Pairs Shortest Paths	2023	Michal Dory Sebastian Förster Yael Kirkpatrick Yasamin Nazari Virginia Vassilevska Williams Tijn de Vos
+ PDF Chat	Improved All-Pairs Approximate Shortest Paths in Congested Clique	2024	Hong Duc Bui Shashwat Chandra Yi‐Jun Chang Michal Dory Dean Leitersdorf
+ PDF Chat	Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles	2022	Mina Dalirrooyfard Ce Jin Virginia Vassilevska Williams Nicole Wein
+ PDF Chat	Linear-Time Online Algorithm Inferring the Shortest Path from a Walk	2018	Shintaro Narisada Diptarama Hendrian Ryo Yoshinaka Ayumi Shinohara
+ PDF Chat	Faster Approximate All Pairs Shortest Paths	2024	Barna Saha Christopher Ye
+	Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs	2014	Matúš Mihaľák Rastislav Šrámek Peter Widmayer
+	Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles	2022	Mina Dalirooyfard Ce Jin Virginia Vassilevska Williams Nicole Wein
+ PDF Chat	Efficient construction of directed hopsets and parallel approximate shortest paths	2020	Nairen Cao Jeremy T. Fineman Katina Russell
+	Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths	2019	Nairen Cao Jeremy T. Fineman Katina Russell
+	Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graph	2010	Neelesh Khanna Surender Baswana
+	Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graph	2010	Neelesh Khanna Surender Baswana
+	Exact and approximate algorithms for the calculation of shortest paths	2006	Fajie Li Reinhard Klette
+ PDF Chat	Decremental all-pairs shortest paths in deterministic near-linear time	2021	Julia Chuzhoy
+ PDF Chat	All-Hops Shortest Paths	2024	Virginia Vassilevska Williams Zoe Xi Yinzhan Xu Uri Zwick
+ PDF Chat	Parameterized Complexity of Finding Dissimilar Shortest Paths	2024	Ryo Funayama Yasuaki Kobayashi Takeaki Uno
+ PDF Chat	Massively Parallel Algorithms for Approximate Shortest Paths	2024	Michal Dory Shaked Matar

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors