Shortest path queries in planar graphs

DOI10.1145/335305.335359MaRDI QIDQ3192016zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, Jinhui Xu

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335359

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Multiple-source shortest paths in planar graphs
• Short path queries in planar graphs in constant time
• scientific article; zbMATH DE number 176745
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Planar graphs, negative weight edges, shortest paths, and near linear time

Cited in

(31)

• An external memory data structure for shortest path queries
• Shortest beer path queries in digraphs with bounded treewidth
• scientific article; zbMATH DE number 7559259 (Why is no real title available?)
• scientific article; zbMATH DE number 7561410 (Why is no real title available?)
• Automata, Languages and Programming
• Multiple-source shortest paths in planar graphs
• A substring-substring LCS data structure
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Many distances in planar graphs
• Algorithms and Computation
• A note on reachability and distance oracles for transmission graphs
• Shortest path queries in digraphs of small treewidth
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Exact distance oracles for planar graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• A face cover perspective to _1 embeddings of planar graphs
• Almost optimal exact distance oracles for planar graphs
• scientific article; zbMATH DE number 7561636 (Why is no real title available?)
• Shortest-path queries in static networks
• Short path queries in planar graphs in constant time
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Faster shortest-path algorithms for planar graphs
• Querying approximate shortest paths in anisotropic regions
• Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Improved distance queries in planar graphs
• Reachability oracles for directed transmission graphs
• Refined vertex sparsifiers of planar graphs
• Shortcutting Planar Digraphs
• Non-crossing shortest paths in undirected unweighted planar graphs in linear time
• Efficient algorithms for shortest path queries in planar digraphs

This page was built for publication: Shortest path queries in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192016)