Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
From MaRDI portal
Publication:3801095
Recommendations
Cited in
(only showing first 100 items - show all)- Optimal decremental connectivity in planar graphs
- Minimum vertex cover in ball graphs through local search
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Flow in planar graphs with vertex capacities
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- Min-cuts and shortest cycles in planar graphs in \(O(n \log\log n)\) time
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Short and simple cycle separators in planar graphs
- Global minimum cuts in surface embedded graphs
- Local search is a PTAS for feedback vertex set in minor-free graphs
- An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
- Fast generation of some classes of planar graphs
- Reachability oracles for directed transmission graphs
- Optimally fast shortest path algorithms for some classes of graphs
- Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem
- I/O-efficient path traversal in succinct planar graphs
- Improved approximation algorithms for box contact representations
- Shortcutting Planar Digraphs
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- Efficient algorithms for shortest path queries in planar digraphs
- Shortest path algorithms for nearly acyclic directed graphs
- The within-strip discrete unit disk cover problem
- An external memory data structure for shortest path queries
- Structured recursive separator decompositions for planar graphs in linear time
- Shortest path computations in source-deplanarized graphs
- Electrical flows over spanning trees
- On fast planning of suboptimal paths amidst polygonal obstacles in plane
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces
- Dynamic algorithms for shortest paths in planar graphs
- An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
- A survey of geodesic paths on 3D surfaces
- 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
- Capacitated discrete unit disk cover
- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Faster shortest paths in dense distance graphs, with applications
- 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
- Improved results on geometric hitting set problems
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Faster shortest-path algorithms for planar graphs
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- The planar multiterminal cut problem
- Approximation algorithms for polynomial-expansion and low-density graphs
- A framework for 1-D compaction with forbidden region avoidance
- Faster approximate diameter and distance oracles in planar graphs
- Computing optimal shortcuts for networks
- scientific article; zbMATH DE number 7561369 (Why is no real title available?)
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- scientific article; zbMATH DE number 7376034 (Why is no real title available?)
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Many distances in planar graphs
- Fast and efficient solution of path algebra problems
- Single source shortest paths in H-minor free graphs
- An efficient oracle for counting shortest paths in planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- Bounded-degree plane geometric spanners in practice
- A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
- Faster network algorithms based on graph decomposition
- A note on reachability and distance oracles for transmission graphs
- Shortest path algorithms for nearly acyclic directed graphs
- Call routing and the ratcatcher
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- Shortest path queries in digraphs of small treewidth
- Fault-tolerant distance labeling for planar graphs
- Fault-tolerant distance labeling for planar graphs
- A fast algorithm for maximum integral two-commodity flow in planar graphs
- Minimal connected enclosures on an embedded planar graph
- 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
- Exact distance oracles for planar graphs
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- An improved line-separable algorithm for discrete unit disk cover
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Approximation algorithms for maximum independent set of pseudo-disks
- On the discrete unit disk cover problem
- Simple PTAS's for families of graphs excluding a minor
- Two-level heaps: a new priority queue structure with applications to the single source shortest path problem
- 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
- Faster algorithms for shortest path and network flow based on graph decomposition
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- The fastest itinerary in time-dependent decentralized travel information systems
- The power of vertex sparsifiers in dynamic graph algorithms
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Local search strikes again: PTAS for variants of geometric covering and packing
- On the negative cost girth problem in planar networks
- Counting and sampling minimum cuts in genus g graphs
- Sublinear separators, fragility and subexponential expansion
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)
