Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Algorithms for multicommodity flows in planar graphs
- The planar multiterminal cut problem
- A framework for 1-D compaction with forbidden region avoidance
- On the integral plane two-commodity flow problem
- Shortest path algorithms for nearly acyclic directed graphs
- Minimal connected enclosures on an embedded planar graph
- A fast algorithm for maximum integral two-commodity flow in planar graphs
- Flow in planar graphs with vertex capacities
- Call routing and the ratcatcher
- On fast planning of suboptimal paths amidst polygonal obstacles in plane
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Faster network algorithms based on graph decomposition
- Optimal decremental connectivity in planar graphs
- Faster shortest paths in dense distance graphs, with applications
- Fast and efficient solution of path algebra problems
- A linear-time algorithm for edge-disjoint paths in planar graphs
- An external memory data structure for shortest path queries
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- Searching among intervals and compact routing tables
- All-pairs-shortest-length on strongly chordal graphs
- Faster approximate diameter and distance oracles in planar graphs
- Computing optimal shortcuts for networks
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- Electrical flows over spanning trees
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Minimum vertex cover in ball graphs through local search
- Subregion graph: a path planning acceleration structure for characters with various motion types in very large environments
- Reachability oracles for directed transmission graphs
- Simple PTAS's for families of graphs excluding a minor
- The fastest itinerary in time-dependent decentralized travel information systems
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Fast generation of some classes of planar graphs
- Succinct and Implicit Data Structures for Computational Geometry
- A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
- Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- On the discrete unit disk cover problem
- Min-cuts and shortest cycles in planar graphs in O(n n) time
- Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem
- An improved line-separable algorithm for discrete unit disk cover
- Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
- Optimally fast shortest path algorithms for some classes of graphs
- Planar graph decomposition and all pairs shortest paths
- Approximation algorithms for maximum independent set of pseudo-disks
- On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
- Approximation algorithms for polynomial-expansion and low-density graphs
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Searching among intervals and compact routing tables
- Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
- Shortest path queries in digraphs of small treewidth
- Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
- Counting and sampling minimum cuts in genus g graphs
- Shortcutting Planar Digraphs
- scientific article; zbMATH DE number 7376034 (Why is no real title available?)
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
- Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- Computing optimal shortcuts for networks
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Faster Approximate Diameter and Distance Oracles in Planar Graphs
- The power of vertex sparsifiers in dynamic graph algorithms
- Shortest-path queries in static networks
- I/O-efficient path traversal in succinct planar graphs
- Improved approximation algorithms for box contact representations
- Faster algorithms for shortest path and network flow based on graph decomposition
- Short and simple cycle separators in planar graphs
- The within-strip discrete unit disk cover problem
- On the discrete unit disk cover problem
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- Structured recursive separator decompositions for planar graphs in linear time
- Exact distance oracles for planar graphs
- Single source distance oracle for planar digraphs avoiding a failed node or link
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- Global minimum cuts in surface embedded graphs
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
- Minimum Cuts in Surface Graphs
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Faster shortest-path algorithms for planar graphs
- Faster shortest-path algorithms for planar graphs
- Fault-tolerant distance labeling for planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- Capacitated discrete unit disk cover
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Local search strikes again: PTAS for variants of geometric covering and packing
- Many distances in planar graphs
- Fault-tolerant distance labeling for planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces
- Improved results on geometric hitting set problems
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)
