Searching among intervals and compact routing tables

DOI10.1007/BF01955044zbMath0846.68025OpenAlexW2077996575MaRDI QIDQ1913700

Greg N. Frederickson

Publication date: 27 May 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01955044

zbMATH Keywords

shortest pathscompact routing tablesweighted directed graphssuccinct encodingpredecessor finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ Area-efficient planar straight-line drawings of outerplanar graphs ⋮ Linear-time algorithms for parametric minimum spanning tree problems on planar graphs ⋮ Splitting plane graphs to outerplanarity ⋮ Untangling circular drawings: algorithms and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Designing networks with compact routing tables
• Implicit data structures for fast search and update
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Storing a sparse table
• Labelling and Implicit Routing in Networks
• Shortest-path algorithms: Taxonomy and annotation
• Implicit data structures for weighted elements
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Should Tables Be Sorted?
• Implicit Data Structures for the Dictionary Problem
• New Bounds on the Complexity of the Shortest Path Problem
• Design and implementation of an efficient priority queue
• Planar graph decomposition and all pairs shortest paths
• Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems
• A Theorem on Boolean Matrices

This page was built for publication: Searching among intervals and compact routing tables