Partitioning graphs to speedup Dijkstra's algorithm

No abstract is available for this paper.

• Publication year

  2007

• Venue

  ACM Journal of Experimental Algorithmics

• Publication date

  2007-02-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1187436.1216585
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Geometric containers for efficient shortest-path computation

  2005cited by this paper
• Computing the shortest path: A search meets graph theory

  2005cited by this paper
• Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005

  2005cited by this paper
• Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, ALENEX /ANALCO 2005, Vancouver, BC, Canada, 22 January 2005

  2005cited by this paper
• Timetable information and shortest paths

  2005cited by this paper
• Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings

  2005cited by this paper
• Engineering shortest paths and layout algorithms for large graphs

  2005cited by this paper
• Acceleration of Shortest Path and Constrained Shortest Path Computation

  2005cited by this paper
• Drawing Graphs to Speed Up Shortest-Path Computations

  2005cited by this paper
• Highway Hierarchies Hasten Exact Shortest Path Queries

  2005cited by this paper
• Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005, Proceedings

  2005cited by this paper
• Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, New Orleans, LA, USA, January 10, 2004

  2004cited by this paper
• Combining speed-up techniques for shortest-path computations

  2004cited by this paper
• Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks

  2004cited by this paper
• Experimental and efficient algorithms : third International Workshop, WEA 2004, Angra dos Reis, Brazil, May 25-28, 2004 : proceedings

  2004cited by this paper
• Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs

  2003influential reference
• Algorithms -- ESA 2003 : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003 : proceedings

  2003cited by this paper
• Deterministic Rendezvous in Graphs

  2003cited by this paper
• Hierarchical speed-up techniques for shortest-path algorithms

  2003cited by this paper
• Experimental and Efficient Algorithms

  2003cited by this paper
• Algorithms - ESA 2001 : 9th Annual European Symposium, Århus, Denmark, August 28-31, 2001 : proceedings

  2001cited by this paper
• Introduction to Algorithms, 2nd edition.

  2001cited by this paper
• Dijkstra's algorithm on-line: an empirical case study from public railroad transport

  1999cited by this paper
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

  1998cited by this paper
• Approximating Shortest Paths in Large-Scale Networks with an Application to Intelligent Transportation Systems

  1998cited by this paper
• LEDA: a platform for combinatorial and geometric computing

  1997cited by this paper
• HiTi graph model of topographical road maps in navigation systems

  1996cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Proceedings of the Twelfth International Conference on Data Engineering, February 26 - March 1, 1996, New Orleans, Louisiana

  1996cited by this paper
• Implicit Routing and Shortest Path Information (Extended Abstract)

  1995cited by this paper
• Modelling a Hierarchy of Space Applied to Large Road Networks

  1994cited by this paper
• Algorithms for Searching Massive Graphs

  1994cited by this paper
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

  1987cited by this paper
• Fibonacci heaps and their uses in improved network optimization algorithms

  1984cited by this paper
• Efficient Algorithms for Shortest Paths in Sparse Networks

  1977cited by this paper
• A note on two problems in connexion with graphs

  1959cited by this paper

• Algorithmically-designed reward shaping for multiagent reinforcement learning in navigation

  2025cites this paper
• Assessing the complexity of a path search optimization method based on clustering for a transport graph

  2025cites this paper
• Connected Partitions via Connected Dominating Sets

  2025cites this paper
• Shortest Path Speed-up Through Binary Image Downsampling

  2024cites this paper
• Route and charging planning for electric vehicles: a multi-objective approach

  2024cites this paper
• Enactment analysis of classification method for voting in traffic prediction

  2024cites this paper
• Polestar++: An Intelligent Routing Engine for National-Wide Public Transportation

  2023cites this paper
• A Universal Scheme for Partitioned Dynamic Shortest Path Index

  2023cites this paper
• Algorithm for the Accelerated Calculation of Conceptual Distances in Large Knowledge Graphs

  2023cites this paper
• A Universal Scheme for Dynamic Partitioned Shortest Path Index: Survey, Improvement, and Experiments

  2023cites this paper
• Improving the Scalability of Distributed Network Emulations: An Algorithmic Perspective

  2023cites this paper
• Efficient and Reconfigurable Optimal Planning in Large-Scale Systems Using Hierarchical Finite State Machines

  2023cites this paper
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs

  2022cites this paper
• Hierarchical Finite State Machines for Efficient Optimal Planning in Large-scale Systems

  2022cites this paper
• Evaluation of Local Search Heuristics for Graph Partitioning with Large k

  2022cites this paper
• Dijkstras algorithm with predictions to solve the single-source many-targets shortest-path problem

  2021cites this paper
• Connected $k$-partition of $k$-connected graphs and $c$-claw-free graphs

  2021cites this paper
• DMGA: A Distributed Shortest Path Algorithm for Multistage Graph

  2021cites this paper
• An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network

  2021cites this paper
• A novel pseudo‐polynomial approach for shortest path problems

  2021cites this paper
• Engineering of Algorithms for Very Large k Partitioning

  2021cites this paper
• Polestar: An Intelligent, Efficient and National-Wide Public Transportation Routing Engine

  2020cites this paper
• Alternativa de cable aéreo en la ciudad de Manizales

  2020cites this paper
• Improved algorithms for map rendering and route planning

  2020influential citation
• Constructing Effective Caches of Shortest Path Queries on Road Networks

  2020cites this paper
• Retracted: A novel pseudo‐polynomial approach for shortest paths problems

  2020cites this paper
• Fast Query Decomposition for Batch Shortest Path Processing in Road Networks

  2020cites this paper
• Faster and Better Nested Dissection Orders for Customizable Contraction Hierarchies

  2019cites this paper
• Ridesharing with Multiple Riders

  2019cites this paper
• Combining the Connection Scan Algorithm with Contraction Hierarchies

  2019cites this paper
• Approximating Balanced Graph Partitions

  2019cites this paper
• A Novel Solution for Simultaneously Finding the Shortest and Possible Paths in Complex Networks

  2019cites this paper
• Efficient Batch Processing of Shortest Path Queries in Road Networks

  2019cites this paper
• Travel Plans in Public Transit Networks Using Artificial Intelligence Planning Models

  2019cites this paper
• A topographically preserved road‐network tile model and optimal routing method for virtual globes

  2019cites this paper
• Institutional Knowledge at Singapore Management University Shortest Path Computation with No Information Leakage

  2019cites this paper
• Design and Implementation of a Narrow-Band Intersatellite Network with Limited Onboard Resources for IoT

  2019cites this paper
• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions

  2019cites this paper
• FedS: Towards Traversing Federated RDF Graphs

  2018cites this paper
• Multi-Modal Route Planning in Road and Transit Networks

  2018influential citation
• ILP-Based Local Search for Graph Partitioning

  2018cites this paper
• Proxies for Shortest Path and Distance Queries

  2017cites this paper
• Computing time dependent travel times in vehicle routing problems

  2017cites this paper
• SHORTEST PATHS ON DYNAMIC GRAPHS: A SURVEY

  2017cites this paper
• A QoC‐based model for performance and QoE trade‐off in distributed systems

  2017cites this paper
• A Survey of Shortest-Path Algorithms

  2017cites this paper
• Efficient Spatial Keyword Query Processing in the Internet of Industrial Vehicles

  2017cites this paper
• A Multi-Modal and Multi-Objective Journey Planner for Integrating Carpooling and Public Transport

  2017cites this paper
• Local re-adjustment based approaches for load balanced network voronoi diagram

  2017cites this paper
• “Nearest Zero-Point” Algorithm for Cooperative Robotic Search Missions

  2017cites this paper
• Computational study on a branch decomposition based exact distance oracle for planar graphs

  2017cites this paper
• A Dijkstra-Based Algorithm for Selecting the Shortest-Safe Evacuation Routes in Dynamic Environments (SSER)

  2017cites this paper
• 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2016, Aarhus, Denmark, August 25, 2016

  2016cites this paper
• Trip-Based Public Transit Routing Using Condensed Search Trees

  2016cites this paper
• Using Quadrilaterals to Compute the Shortest Path

  2016cites this paper
• On-the-Fly Nearest-Shelter Computation in Event-Dependent Spatial Networks in Disasters

  2016cites this paper
• Fuel-Efficient Centralized Coordination of Truck Platooning

  2016cites this paper
• Graph-based Analysis of Dynamic Systems

  2016cites this paper
• Determining an optimal path for forest road construction using Dijkstra’s algorithm

  2016cites this paper
• Survey on Mining Shortest Path in Directed and Dynamic Graphs

  2016cites this paper
• Spatial Keyword Query Processing in the Internet of Vehicles

  2016cites this paper
• Proxies for Shortest Path and Distance Queries

  2016influential citation
• PROVIDING ONLINE SHORTEST PATH BASED ON LIVE TRAFFIC CIRCUMSTANCES

  2015cites this paper
• Alternative Route Techniques and their Applications to the Stochastics on-time Arrival Problem

  2015cites this paper
• Solving Medium Scale Instances of the Cable-Trench Problem: Applied to the Proposed LOFAR Super Station in Nancay, France

  2015cites this paper
• Route Planning in Transportation Networks

  2015cites this paper
• GISCUP 2015 : Notes on Routing with Polygonal Constraints

  2015cites this paper
• An Analytical Study of Com putation and Com munication Tradeo ffs in Distributed Graph Processing Systems

  2015cites this paper
• Map stream: Initializing what-if analyses for real-time symbiotic traffic simulations

  2014cites this paper
• Fully dynamic update of arc‐flags

  2014cites this paper
• The Shortest Path Problem on Real Road Networks: Theory, Algorithms and Computations

  2014cites this paper
• Shortest-path queries in static networks

  2014cites this paper
• The Shortest-Path Problem: Analysis and Comparison of Methods

  2014cites this paper
• An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication

  2014cites this paper
• Distance Landmarks Revisited for Road Graphs

  2014influential citation
• A speedup technique for dynamic graphs using partitioning strategy and multithreaded approach

  2014cites this paper
• Algorithm for shortest path search in Geographic Information Systems by using reduced graphs

  2013cites this paper
• Routing directions: keeping it fast and simple

  2013cites this paper
• Optimizing Landmark-Based Routing and Preprocessing

  2013cites this paper
• Algorithm Engineering for Realistic Journey Planning in Transportation Networks

  2013cites this paper
• Vision guided path planning system for vehicles using infrared landmark

  2013cites this paper
• Candidate Sets for Alternative Routes in Road Networks (Extended Abstract)

  2013cites this paper
• Strong location privacy: A case study on shortest path queries

  2013cites this paper
• Recent Advances in Graph Partitioning

  2013cites this paper
• Building Blocks for Mapping Services

  2013cites this paper
• Path Planning under Failures in Wireless Sensor Networks

  2013cites this paper
• Integration of UAV in Flight and Ground Operations

  2013cites this paper
• Development of an iPhone-controlled UAV

  2013cites this paper
• Facilitating Eco-Routing via Spatial Big Data : A Case-Study on Temporally-Detailed Roadmaps

  2013cites this paper
• KaHIP v0.53 - Karlsruhe High Quality Partitioning - User Guide

  2013cites this paper
• Algorithms for the Widest Path Problem

  2013cites this paper
• Incremental Updates of Contraction Hierarchies for Road Network Routing

  2013cites this paper
• A Smoothest Path algorithm and its visualization tool

  2013cites this paper
• Kürzeste Wege im Wikipedia-Linkgraph

  2013cites this paper
• Experimental Algorithms

  2012influential citation
• Doing More for Less ∗ - Cache-Aware Parallel Contraction

  2012cites this paper
• Doing More for Less -- Cache-Aware Parallel Contraction Hierarchies Preprocessing

  2012cites this paper
• High quality graph partitioning

  2012cites this paper
• III : Small : Investigating Spatial Big Data for Next Generation Routing Services

  2012cites this paper
• The UNB-RISC16 Object File Format

  2012cites this paper