Space-time trade-offs for stack-based algorithms

DOI10.1007/s00453-014-9893-5zbMath1328.68290OpenAlexW2125293312MaRDI QIDQ494797

Matias Korman, Stefan Langerman, Kunihiko Sadakane, Luis Barba, Rodrigo I. Silveira

Publication date: 2 September 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9893-5

zbMATH Keywords

constant workspacespace-time trade-offmemory-constrained algorithmsstack algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (14)

Time-space trade-offs for triangulations and Voronoi diagrams ⋮ Optimal In-place Algorithms for Basic Graph Problems ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ A new balanced subdivision of a simple polygon for time-space trade-off algorithms ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon ⋮ A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Space efficient linear time algorithms for BFS, DFS and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a visibility polygon using few variables
• Selection from read-only memory and sorting with minimum data movement
• Multi-pass geometric algorithms
• Upper bounds for time-space trade-offs in sorting and selection
• Corrections to Lee's visibility polygon algorithm
• Selection and sorting with limited storage
• Triangulating a simple polygon in linear time
• Triangulating a simple polygon
• Implementation and evaluation of decision trees with range and region splitting
• On the solution of linear recurrence equations
• Optimal shortest path queries in a simple polygon
• Memory-constrained algorithms for simple polygons
• Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
• Linear time algorithm for approximating a curve by a single-peaked curve
• On the identification of the convex hull of a finite set of points in the plane
• Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons
• Space-Time Trade-offs for Stack-Based Algorithms
• The recognition of deterministic CFLs in small time and space
• On finding the convex hull of a simple polygon
• Data Mining with optimized two-dimensional association rules
• Parallel RAMs with owned global memory and deterministic context-free language recognition
• Improved upper bounds for time-space tradeoffs for selection with limited storage
• Computational Complexity
• Visibility Algorithms in the Plane

This page was built for publication: Space-time trade-offs for stack-based algorithms