Bidirectional Dijkstra’s Algorithm is Instance-Optimal

Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan, Jakub Tětek

Type: Book-Chapter

Publication Date: 2025-01-01

Citations: 0

DOI: https://doi.org/10.1137/1.9781611978315.16

View Publication

Download PDF

Locations

arXiv (Cornell University) - View - PDF
Society for Industrial and Applied Mathematics eBooks - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Bidirectional Dijkstra's Algorithm is Instance-Optimal	2024	Bernhard Haeupler Richard Hladík Václav Rozhoň Robert E. Tarjan Jakub Tětek
+	Bidirectional edges problem: Part I—A simple algorithm	1996	Bud Mishra
+ PDF Chat	Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm	2016	Stefan Hougardy Jannik Silvanus Jens Vygen
+ PDF Chat	Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem	2010	Hyung-Chan An Robert Kleinberg David B. Shmoys
+	On an instance of the inverse shortest paths problem	1992	D. Burton Philippe L. Toint
+	Bidirectional Heuristic Search Reconsidered	1997	Hermann Kaindl Gerhard Kainz
+ PDF Chat	Bidirectional Heuristic Search Reconsidered	1997	Hermann Kaindl Gerhard Kainz
+ PDF Chat	Subgraph Matching via Partial Optimal Transport	2024	Wen-Xin Pan Isabel Haasler Pascal Frossard
+	Fast Primal-Dual Update against Local Weight Update in Linear Assignment Problem and Its Application	2022	Morita Kohei Shinya Shiroshita Yutaro Yamaguchi Yu Yokoi
+	Travelling Salesman Problem - Parallel Algorithms	1995	Ewa Dudek-Dyducb Tadeusz Dyducb
+ PDF Chat	Linear-Time Online Algorithm Inferring the Shortest Path from a Walk	2018	Shintaro Narisada Diptarama Hendrian Ryo Yoshinaka Ayumi Shinohara
+	P-optimal heuristics	1980	Karl Lieberherr
+ PDF Chat	Lower Bounds for Non-adaptive Shortest Path Relaxation	2023	David Eppstein
+	Approximate algorithms for the traveling salesman problem. II	2015	S. I. Sergeev
+	An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem	2019	Chaitanya K. Joshi Thomas Laurent Xavier Bresson
+	Targeted Multiobjective Dijkstra Algorithm	2021	Pedro Maristany de las Casas Luitgard Kraus Antonio Sedeño‐Noda Ralf Borndörfer
+ PDF Chat	Resource Constrained Pathfinding with Enhanced Bidirectional A* Search	2024	Saman Ahmadi Andrea Raith Guido Tack Mahdi Jalili
+ PDF Chat	Solving the At-Most-Once Problem with Nearly Optimal Effectiveness	2012	Sotirios Kentros Aggelos Kiayias
+ PDF Chat	Solving the at-most-once problem with nearly optimal effectiveness	2013	Sotirios Kentros Aggelos Kiayias
+	Bi-objective Search with Bi-directional A*	2021	Saman Ahmadi Guido Tack Daniel Harabor Philip Kilby

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors