Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

DOI10.1137/0216064zbMATH Open0654.68087OpenAlexW2120424341MaRDI QIDQ3801095FDOQ3801095

Authors: Greg N. Frederickson 

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b8fa2dfb538111767547c1c79daee6f9efd3b9ce

Recommendations

• Faster shortest-path algorithms for planar graphs
• Faster shortest-path algorithms for planar graphs
• Faster shortest paths in dense distance graphs, with applications
• Dynamic algorithms for shortest paths in planar graphs
• scientific article; zbMATH DE number 219245

zbMATH Keywords

decision treesdata structuresmaximum flowminimum cutplanar graphsmulticommodity flowall pairs shortest pathsheapssingle source shortest pathsplanar separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Paths and cycles (05C38)

Cited In (only showing first 100 items - show all)

• An external memory data structure for shortest path queries
• Shortest path computations in source-deplanarized graphs
• On fast planning of suboptimal paths amidst polygonal obstacles in plane
• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• Capacitated discrete unit disk cover
• Dynamic algorithms for shortest paths in planar graphs
• A survey of geodesic paths on 3D surfaces
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Balanced independent and dominating sets on colored interval graphs
• How to catch marathon cheaters: new approximation algorithms for tracking paths
• On the dilation spectrum of paths, cycles, and trees
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Faster shortest-path algorithms for planar graphs
• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Improved results on geometric hitting set problems
• The planar multiterminal cut problem
• Title not available (Why is that?)
• A framework for 1-D compaction with forbidden region avoidance
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Many distances in planar graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• Fast and efficient solution of path algebra problems
• Single source shortest paths in \(H\)-minor free graphs
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• Shortest path algorithms for nearly acyclic directed graphs
• Shortest path queries in digraphs of small treewidth
• Call routing and the ratcatcher
• A fast algorithm for maximum integral two-commodity flow in planar graphs
• Minimal connected enclosures on an embedded planar graph
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• An improved line-separable algorithm for discrete unit disk cover
• On the discrete unit disk cover problem
• Simple PTAS's for families of graphs excluding a minor
• Approximation algorithms for maximum independent set of pseudo-disks
• Two-level heaps: a new priority queue structure with applications to the single source shortest path problem
• Planar graphs, negative weight edges, shortest paths, and near linear time
• On the negative cost girth problem in planar networks
• Counting and sampling minimum cuts in genus \(g\) graphs
• Shortest-path queries in static networks
• Sublinear separators, fragility and subexponential expansion
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Faster shortest-path algorithms for planar graphs
• On the discrete unit disk cover problem
• Splitting (complicated) surfaces is hard
• Minimum Cuts in Surface Graphs
• All-pairs-shortest-length on strongly chordal graphs
• Searching among intervals and compact routing tables
• Planar graph decomposition and all pairs shortest paths
• Algorithms for multicommodity flows in planar graphs
• A distributed shortest path algorithm for a planar network
• Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
• A linear-time algorithm for edge-disjoint paths in planar graphs
• On the integral plane two-commodity flow problem
• Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
• Minimum vertex cover in ball graphs through local search
• Flow in planar graphs with vertex capacities
• Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
• Global minimum cuts in surface embedded graphs
• Optimally fast shortest path algorithms for some classes of graphs
• Fast generation of some classes of planar graphs
• I/O-efficient path traversal in succinct planar graphs
• Improved approximation algorithms for box contact representations
• Shortcutting Planar Digraphs
• Structured recursive separator decompositions for planar graphs in linear time
• The within-strip discrete unit disk cover problem
• An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
• Electrical flows over spanning trees
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Faster shortest paths in dense distance graphs, with applications
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Approximation algorithms for polynomial-expansion and low-density graphs
• Title not available (Why is that?)
• Faster approximate diameter and distance oracles in planar graphs
• Computing optimal shortcuts for networks
• Title not available (Why is that?)
• Bounded-degree plane geometric spanners in practice
• An efficient oracle for counting shortest paths in planar graphs
• An efficient oracle for counting shortest paths in planar graphs
• A note on reachability and distance oracles for transmission graphs
• Faster network algorithms based on graph decomposition
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Fault-tolerant distance labeling for planar graphs
• Fault-tolerant distance labeling for planar graphs
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Exact distance oracles for planar graphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• An efficient parallel algorithm for shortest paths in planar layered digraphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• PTASs for secure dominating set in planar graphs and growth-bounded graphs
• Single source distance oracle for planar digraphs avoiding a failed node or link
• Searching among intervals and compact routing tables
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Faster algorithms for shortest path and network flow based on graph decomposition

This page was built for publication: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

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