Faster shortest-path algorithms for planar graphs
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Faster shortest-path algorithms for planar graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Faster shortest paths in dense distance graphs, with applications
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
Cited in
(37)- The planar multiterminal cut problem
- A uniform approach to semi-dynamic problems on digraphs
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Decomposable multi-parameter matroid optimization problems.
- Semi-dynamic breadth-first search in digraphs
- Faster shortest paths in dense distance graphs, with applications
- A linear-time algorithm for edge-disjoint paths in planar graphs
- An external memory data structure for shortest path queries
- Maximum matchings in planar graphs via Gaussian elimination
- Improved algorithms for replacement paths problems in restricted graphs
- Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
- Fast generation of some classes of planar graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
- Finding the k Shortest Paths
- Optimally fast shortest path algorithms for some classes of graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n \log^2 n)\)-time algorithm
- On algorithms employing treewidth for L-bounded cut problems
- Shortest path queries in digraphs of small treewidth
- Shortcutting Planar Digraphs
- Encoding shortest paths in spatial networks
- A strongly polynomial time algorithm for the shortest path problem on coherent planar periodic graphs
- Semi-dynamic shortest paths and breadth-first search in digraphs
- A new approach for solving the network problems
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- An efficient algorithm for shortest paths in vertical and horizontal segments
- Faster algorithms for shortest path and network flow based on graph decomposition
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Faster shortest-path algorithms for planar graphs
- Inserting Multiple Edges into a Planar Graph
- Fast separator decomposition for finite element meshes
- Counting edges in a dag
- Efficient algorithms for shortest path queries in planar digraphs
- Shortest path computations in source-deplanarized graphs
- A distributed shortest path algorithm for a planar network
- An algorithm for computing simple \(k\)-factors
This page was built for publication: Faster shortest-path algorithms for planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890838)
