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

DOI10.7155/JGAA.00240MaRDI QIDQ2865044zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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
• Reprint of: Memory-constrained algorithms for simple polygons
• Memory efficient algorithms for cactus graphs and block graphs

Describes a project that uses

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)