Planar graphs, negative weight edges, shortest paths, and near linear time
From MaRDI portal
Publication:2496320
DOI10.1016/j.jcss.2005.05.007zbMath1103.68091OpenAlexW2768149714MaRDI QIDQ2496320
Publication date: 12 July 2006
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.05.007
Related Items
Minimum Cuts in Surface Graphs, Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time, NC Algorithms for Weighted Planar Perfect Matching and Related Problems, Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, On the negative cost girth problem in planar networks, Unnamed Item, Faster shortest paths in dense distance graphs, with applications, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Unnamed Item, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Decremental SPQR-trees for Planar Graphs, Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs, Shortest-path queries in static networks, Computing large matchings in planar graphs with fixed minimum degree, Single source shortest paths in \(H\)-minor free graphs, Unnamed Item, Unnamed Item, Unnamed Item, Level-planar drawings with few slopes, Fault-tolerant distance labeling for planar graphs, Min-Cost Flow in Unit-Capacity Planar Graphs, Accelerated Bend Minimization, Single-source shortest paths and strong connectivity in dynamic planar graphs, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Many distances in planar graphs, Engineering Route Planning Algorithms, Non-crossing shortest paths in undirected unweighted planar graphs in linear time, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Unnamed Item, Unnamed Item, Fault-tolerant distance labeling for planar graphs, Short and Simple Cycle Separators in Planar Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Finding small simple cycle separators for 2-connected planar graphs
- The Discrete Geodesic Problem
- On a routing problem
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- Using Interior-Point Methods for Fast Parallel Algorithms for Bipartite Matching and Related Problems
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
- Faster Scaling Algorithms for Network Problems
- Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
- Flow in Planar Graphs with Multiple Sources and Sinks
- Compact oracles for reachability and approximate distances in planar digraphs
- Faster shortest-path algorithms for planar graphs
