HackerPapers

arXiv:2502.10519cs.DS

Customizable Contraction Hierarchies -- A Survey

Thomas Bläsius, Valentin Buchhold, Dorothea Wagner, Tim Zeitz, Michael Zündorf

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

This work establishes the technical fundamentals of a well-tuned Customizable Contraction Hierarchies (CCH) implementation that is simple and elegant. We give a detailed overview of the state of the art of CCH, review recent advances on CCH and show how to combine them. Additionally, we propose further refinements that improve the performance of CCH. An extensive evaluation confirms that a CCH framework is not only comprehensive in supported features but also competitive in performance to both Contraction Hierarchies (CH) and Customizable Route Planning (CRP).

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 1 identifiable commenter in 2 comments across 2 threads, from Oct 2025 to Feb 2026.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. OsmAnd’s Faster Offline Navigation (2025) 1 comment

    • Some of those objections to Contraction Hierarchies are possibly a little out of date. Modern variants of the technique allow for rapid live traffic customisation, see e.g. https://arxiv.org/pdf/2502.10519 . I suspect that the "nested dissection" approach also allows for…

      n4r9View on HNParent context

  2. Move over Dijkstra: New algorithm just rewrote 70 years of computer science 1 comment

    • Hi! If I remember rightly, you can run contraction hierarchies but stop short of the full contraction, and use the core vertices as "hubs"? Hope you don't mind but I took a little look at your posting history and saw this: https://news.ycombinator.com/item?id=41954120 I've been…

      n4r9View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.