Space-time trade-offs for stack-based algorithms
From MaRDI portal
Publication:494797
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
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
