On the public citation graph

Highway Dimension and Provably Efficient Shortest Path Algorithms

0 signed · 118 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5openalex-snapshot
Proximity-preserving labeling schemes
inferredcites →https://doi.org/10.1002/net.20382openalex-snapshot
Experimental study of speed up techniques for timetable information systems
inferredcites →https://doi.org/10.1007/3-540-57155-8_252openalex-snapshot
Algorithms for polytope covering and approximation
inferredcites →https://doi.org/10.1007/978-3-319-21852-6_3openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1007/978-3-540-87744-8_40openalex-snapshot
An Optimal Dynamic Spanner for Doubling Metric Spaces
inferredcites →https://doi.org/10.1007/978-3-642-14355-7_6openalex-snapshot
Synthetic Road Networks
inferredcites →https://doi.org/10.1007/978-3-642-20662-7_20openalex-snapshot
A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
inferredcites →https://doi.org/10.1007/978-3-642-20662-7_32openalex-snapshot
Customizable Route Planning
inferredcites →https://doi.org/10.1007/978-3-642-22006-7_58openalex-snapshot
VC-Dimension and Shortest Path Algorithms
inferredcites →https://doi.org/10.1007/978-3-642-33090-2_4openalex-snapshot
Hierarchical Hub Labelings for Shortest Paths
inferredcites →https://doi.org/10.1007/978-3-642-38527-8_5openalex-snapshot
Faster Customization of Road Networks
inferredcites →https://doi.org/10.1007/978-3-642-38527-8_7openalex-snapshot
Transit Node Routing Reconsidered
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_7openalex-snapshot
Algorithms for Hub Label Optimization
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_9openalex-snapshot
Search-Space Size in Contraction Hierarchies
inferredcites →https://doi.org/10.1007/bf01386390openalex-snapshot
A note on two problems in connexion with graphs
inferredcites →https://doi.org/10.1007/bf02570718openalex-snapshot
Almost optimal set covers in finite VC-dimension
inferredcites →https://doi.org/10.1016/0304-3975(95)00053-yopenalex-snapshot
Semi-metrics, closure spaces and digital topology
inferredcites →https://doi.org/10.1016/j.ipl.2005.03.010openalex-snapshot
Hitting sets when the VC-dimension is small
inferredcites →https://doi.org/10.1016/j.jalgor.2004.05.002openalex-snapshot
Distance labeling in graphs
inferredcites →https://doi.org/10.1016/j.jpdc.2012.02.007openalex-snapshot
PHAST: Hardware-accelerated shortest path trees
inferredcites →https://doi.org/10.1016/s0022-0000(74)80044-9openalex-snapshot
Approximation algorithms for combinatorial problems
inferredcites →https://doi.org/10.1037/e400002009-005openalex-snapshot
The small-world problem
inferredcites →https://doi.org/10.1080/15427951.2004.10129077openalex-snapshot
Detecting a Network Failure
inferredcites →https://doi.org/10.1090/dimacs/074openalex-snapshot
The Shortest Path Problem
inferredcites →https://doi.org/10.1090/dimacs/074/02openalex-snapshot
An experimental evaluation of point-to-point shortest path calculation on road networks with precalculated edge-flags
inferredcites →https://doi.org/10.1090/dimacs/074/03openalex-snapshot
Fast point-to-point shortest path computations with arc-flags
inferredcites →https://doi.org/10.1090/dimacs/074/05openalex-snapshot
Reach for A*: shortest path algorithms with preprocessing
inferredcites →https://doi.org/10.1090/dimacs/074/07openalex-snapshot
Ultrafast shortest-path queries via transit nodes
inferredcites →https://doi.org/10.1090/dimacs/074/08openalex-snapshot
Robust, almost constant time shortest-path queries in road networks
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1109/ipdps.2011.108openalex-snapshot
Graph Partitioning with Natural Cuts
inferredcites →https://doi.org/10.1109/sfcs.1988.21961openalex-snapshot
A Las Vegas algorithm for linear programming when the dimension is small
inferredcites →https://doi.org/10.1109/sfcs.2003.1238226openalex-snapshot
Bounded geometries, fractals, and low-distortion embeddings
inferredcites →https://doi.org/10.1126/science.1137521openalex-snapshot
Fast Routing in Road Networks with Transit Nodes
inferredcites →https://doi.org/10.1137/070698774openalex-snapshot
A Practical Shortest Path Algorithm with Linear Expected Time
inferredcites →https://doi.org/10.1137/1.9781611970265openalex-snapshot
Data Structures and Network Algorithms
inferredcites →https://doi.org/10.1137/1.9781611972924.14openalex-snapshot
Transit Nodes – Lower Bounds and Refined Construction
inferredcites →https://doi.org/10.1137/1.9781611972924.15openalex-snapshot
Robust Mobile Route Planning with Limited Connectivity
inferredcites →https://doi.org/10.1137/1116025openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1137/s0097539702403098openalex-snapshot
Reachability and Distance Queries via 2-Hop Labels
inferredcites →https://doi.org/10.1145/1412228.1412239openalex-snapshot
Engineering multilevel overlay graphs for shortest-path queries
inferredcites →https://doi.org/10.1145/1463434.1463455openalex-snapshot
Studying (non-planar) road networks through an algorithmic lens
inferredcites →https://doi.org/10.1145/1498698.1537599openalex-snapshot
SHARC
inferredcites →https://doi.org/10.1145/1568318.1568322openalex-snapshot
Triangulation and embedding using small sets of beacons
inferredcites →https://doi.org/10.1145/1671970.1671976openalex-snapshot
Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
inferredcites →https://doi.org/10.1145/1989323.1989368openalex-snapshot
On k-skip shortest paths
inferredcites →https://doi.org/10.1145/2133803.2330080openalex-snapshot
Engineering highway hierarchies
inferredcites →https://doi.org/10.1145/2424321.2424365openalex-snapshot
HLDB
inferredcites →https://doi.org/10.1145/2442942.2442949openalex-snapshot
On optimal preprocessing for contraction hierarchies
inferredcites →https://doi.org/10.1145/2444016.2444019openalex-snapshot
Alternative routes in road networks
inferredcites →https://doi.org/10.1145/28869.28874openalex-snapshot
Fibonacci heaps and their uses in improved network optimization algorithms
inferredcites →https://doi.org/10.1145/335305.335325openalex-snapshot
The small-world phenomenon
inferredcites →https://doi.org/10.1145/351827.384254openalex-snapshot
Dijkstra's algorithm on-line
inferredcites →https://doi.org/10.1287/moor.4.3.233openalex-snapshot
A Greedy Heuristic for the Set-Covering Problem
inferredcites →https://doi.org/10.1287/opre.27.1.161openalex-snapshot
Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
inferredcites →https://doi.org/10.1287/trsc.1110.0401openalex-snapshot
Exact Routing in Large Road Networks Using Contraction Hierarchies
inferredcites →https://doi.org/10.4086/toc.2011.v007a005openalex-snapshot
inferredcites →https://doi.org/10.5555/1070432.1070455openalex-snapshot
Computing the shortest path: A search meets graph theory

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/cpe.5644openalex-snapshot
A parallel time‐varying earliest arrival path algorithm for evacuation planning of underground mine water inrush accidents
inferred← citeshttps://doi.org/10.1007/978-3-030-30786-8_14openalex-snapshot
Travelling on Graphs with Small Highway Dimension
inferred← citeshttps://doi.org/10.1007/978-3-030-58150-3_17openalex-snapshot
W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension
inferred← citeshttps://doi.org/10.1007/978-3-030-79987-8_19openalex-snapshot
An Efficient Noisy Binary Search in Graphs via Median Approximation
inferred← citeshttps://doi.org/10.1007/978-3-031-15914-5_16openalex-snapshot
Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension
inferred← citeshttps://doi.org/10.1007/978-3-031-63021-7_34openalex-snapshot
Parameterized Upper Bounds for Path-Consistent Hub Labeling
inferred← citeshttps://doi.org/10.1007/978-3-032-06164-5_1openalex-snapshot
Estimating Accurate Traffic Time by Smart Simulative Route Predictions
inferred← citeshttps://doi.org/10.1007/978-3-032-23187-1_11openalex-snapshot
A Heuristic Approach to Optimal Meeting Points in Multi-modal Ride-Sharing Networks
inferred← citeshttps://doi.org/10.1007/978-3-319-24971-1_7openalex-snapshot
Graph Fill-In, Elimination Ordering, Nested Dissection and Contraction Hierarchies
inferred← citeshttps://doi.org/10.1007/978-3-319-49487-6_2openalex-snapshot
Route Planning in Transportation Networks
inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_47openalex-snapshot
Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_38openalex-snapshot
A $$(1+{\varepsilon })$$ ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_6openalex-snapshot
On the Complexity of Hub Labeling (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/978-3-662-48350-3_84openalex-snapshot
Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-662-48971-0_41openalex-snapshot
Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing
inferred← citeshttps://doi.org/10.1007/978-981-97-0566-5_15openalex-snapshot
Exact and Approximate Hierarchical Hub Labeling
inferred← citeshttps://doi.org/10.1007/s00453-018-0455-0openalex-snapshot
Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
inferred← citeshttps://doi.org/10.1007/s00453-020-00683-wopenalex-snapshot
The Parameterized Hardness of the k-Center Problem in Transportation Networks
inferred← citeshttps://doi.org/10.1007/s00453-020-00785-5openalex-snapshot
Travelling on Graphs with Small Highway Dimension
inferred← citeshttps://doi.org/10.1007/s00453-025-01357-1openalex-snapshot
Generalized $$k$$-Center: Distinguishing Doubling and Highway Dimension
inferred← citeshttps://doi.org/10.1007/s10489-014-0637-7openalex-snapshot
SPORE: shortest path overlapped regions and confined traversals towards graph clustering
inferred← citeshttps://doi.org/10.1007/s10707-024-00533-9openalex-snapshot
Highway systems: How good are they, really?
inferred← citeshttps://doi.org/10.1007/s10878-021-00777-3openalex-snapshot
Sublinear search spaces for shortest path planning in grid and road networks
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.06.002openalex-snapshot
Polynomial time approximation schemes for clustering in low highway dimension graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.07.017openalex-snapshot
Eccentricity queries and beyond using hub labels
inferred← citeshttps://doi.org/10.1061/(asce)hz.2153-5515.0000493openalex-snapshot
Network-of-Networks Framework for Multimodal Hazmat Transportation Risk Mitigation: Application to Used Nuclear Fuel in Canada
inferred← citeshttps://doi.org/10.1093/pnasnexus/pgac313openalex-snapshot
Spatiotemporal reconstruction of ancient road networks through sequential cost–benefit analysis
inferred← citeshttps://doi.org/10.1109/access.2018.2808407openalex-snapshot
IBAS: Index Based A-Star
inferred← citeshttps://doi.org/10.1109/bdcloud.2014.11openalex-snapshot
CORE Analysis for Efficient Shortest Path Traversal Queries in Social Graphs
inferred← citeshttps://doi.org/10.1109/hpec43674.2020.9286141openalex-snapshot
Fast GPU Graph Contraction by Combining Efficient Shallow Searches and Post-Culling
inferred← citeshttps://doi.org/10.1109/iccitechn.2016.7860187openalex-snapshot
Statistical approach based dynamic route selection support system
inferred← citeshttps://doi.org/10.1109/icdew.2015.7129587openalex-snapshot
Traversal optimizations and analysis for large graph clustering
inferred← citeshttps://doi.org/10.1109/tdsc.2021.3126627openalex-snapshot
Fault-Tolerant Routing With Load Balancing in LeTQ Networks
inferred← citeshttps://doi.org/10.1137/16m1067196openalex-snapshot
A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
inferred← citeshttps://doi.org/10.1137/21m1425487openalex-snapshot
Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics
inferred← citeshttps://doi.org/10.1145/2534931.2534938openalex-snapshot
Flexible route guidance through turn instruction graphs
inferred← citeshttps://doi.org/10.1145/2886843openalex-snapshot
Customizable Contraction Hierarchies
inferred← citeshttps://doi.org/10.1145/3293611.3331625openalex-snapshot
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
inferred← citeshttps://doi.org/10.1145/3330345.3330368openalex-snapshot
GPU road network graph contraction and SSSP query
inferred← citeshttps://doi.org/10.1145/3355514openalex-snapshot
Fast Exact Computation of Isocontours in Road Networks
inferred← citeshttps://doi.org/10.1145/3567421openalex-snapshot
Robust Routing Using Electrical Flows
inferred← citeshttps://doi.org/10.1145/3609956.3609963openalex-snapshot
Highway Systems: How Good are They, Really?
inferred← citeshttps://doi.org/10.1145/3701551.3703512openalex-snapshot
A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
inferred← citeshttps://doi.org/10.1287/opre.2021.2166openalex-snapshot
Computing Constrained Shortest-Paths at Scale
inferred← citeshttps://doi.org/10.14569/ijacsa.2016.071048openalex-snapshot
FNN based Adaptive Route Selection Support System
inferred← citeshttps://doi.org/10.1609/aaai.v32i1.12075openalex-snapshot
Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks
inferred← citeshttps://doi.org/10.1609/aaai.v38i18.29987openalex-snapshot
Approximate Distance Oracle for Fault-Tolerant Geometric Spanners
inferred← citeshttps://doi.org/10.1609/icaps.v28i1.13888openalex-snapshot
Scalability of Route Planning Techniques
inferred← citeshttps://doi.org/10.31390/gradschool_dissertations.5104openalex-snapshot
Shortest Path Calculation Using Contraction Hierarchy Graph Algorithms on Nvidia GPUs
inferred← citeshttps://doi.org/10.3390/app14072884openalex-snapshot
Route Planning Algorithms for Fleets of Connected Vehicles: State of the Art, Implementation, and Deployment
inferred← citeshttps://doi.org/10.3390/info13040168openalex-snapshot
Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks
inferred← citeshttps://doi.org/10.3991/ijim.v15i14.19099openalex-snapshot
Adaptive Smart Traffic Accidents Management System
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.143openalex-snapshot
Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond
inferred← citeshttps://doi.org/10.4230/lipics.ipec.2019.4openalex-snapshot
Hierarchy of Transportation Network Parameters and Hardness Results
inferred← citeshttps://doi.org/10.48550/arxiv.1501.02492openalex-snapshot
On the Complexity of Hub Labeling
inferred← citeshttps://doi.org/10.48550/arxiv.1605.02530openalex-snapshot
Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
inferred← citeshttps://doi.org/10.5445/ir/1000035705openalex-snapshot
Building Blocks for Mapping Services
inferred← citeshttps://doi.org/10.70675/2f381c80z8ff9z4c06za271z14c6738fb2d4openalex-snapshot
An Efficient Framework for Processing and Analyzing Unstructured Text to Discover Delivery Delay and Optimization of Route Planning in Realtime
inferred← citeshttps://doi.org/10.70675/eee6d28dzf1b2z4719z9254zac9f957232c6openalex-snapshot
The semiring-based provenance framework for graph databases
inferred← citeshttps://doi.org/10.7939/r3-ved5-js37openalex-snapshot
Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.