Constant-work-space algorithms for shortest paths in trees and simple polygons

DOI10.7155/JGAA.00240zbMATH Open1276.05110OpenAlexW2103678784MaRDI QIDQ2865044FDOQ2865044

Authors: Wolfgang Mulzer, Yajun Wang, Tetsuo Asano 

Publication date: 28 November 2013

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00240

Recommendations

• Constant-work-space algorithm for a shortest path in a simple polygon
• Constant-work-space algorithms for geometric problems
• Memory-constrained algorithms for simple polygons
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Shortest path in a polygon using sublinear space

zbMATH Keywords

computing instead of storingsimulated parallelization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38)

Cited In (10)

• Memory-constrained algorithms for simple polygons
• Constant-work-space algorithms for geometric problems
• Constant-work-space algorithm for a shortest path in a simple polygon
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Space-time trade-offs for stack-based algorithms
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Constant work-space algorithms for facility location problems
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Memory efficient algorithms for cactus graphs and block graphs
• Reprint of: Memory-constrained algorithms for simple polygons

Uses Software

• LEDA

This page was built for publication: Constant-work-space algorithms for shortest paths in trees and simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2865044)