Non-crossing shortest paths lengths in planar graphs in linear time
From MaRDI portal
Publication:6153472
DOI10.1016/J.DAM.2023.12.011OpenAlexW4390139760MaRDI QIDQ6153472FDOQ6153472
Authors: Lorenzo Balzotti, Paolo G. Franciosa 
Publication date: 14 February 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2023.12.011
Recommendations
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Shortest non-crossing walks in the plane
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Multiple-source shortest paths in planar graphs
- Shortest paths in directed planar graphs with negative lengths
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Cites Work
- Preserving order in a forest in less than logarithmic time and linear space
- A linear-time algorithm for a special case of disjoint set union
- A framework for solving VLSI graph layout problems
- Faster shortest-path algorithms for planar graphs
- Shortest non-crossing walks in the plane
- New lower bound techniques for VLSI
- Thick non-crossing paths and minimum-cost flows in polygonal domains
- Multiple-source shortest paths in planar graphs
- Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
- Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
- Non-crossing shortest paths in undirected unweighted planar graphs in linear time
- Max flow vitality in general and \(st\)-planar graphs
- k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
- Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
- Non-crossing shortest paths lengths in planar graphs in linear time
- How vulnerable is an undirected planar graph with respect to max flow
Cited In (1)
This page was built for publication: Non-crossing shortest paths lengths in planar graphs in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153472)
