Space-time trade-offs for stack-based algorithms
From MaRDI portal
Publication:494797
DOI10.1007/S00453-014-9893-5zbMATH Open1328.68290OpenAlexW2125293312MaRDI QIDQ494797FDOQ494797
Authors: Luis Barba, Matias Korman, Stefan Langerman, Kunihiko Sadakane, 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
Recommendations
- Space-time trade-offs for stack-based algorithms
- Time-space tradeoffs for set operations
- Efficient computation of optimal space-time performance curves for memory hierarchies
- Time-space tradeoffs for branching programs
- Time-space trade-offs for branching programs
- scientific article; zbMATH DE number 2149351
- Space Complexity of Stack Automata Models
- Space complexity of stack automata models
- Allocate-on-use space complexity of shared-memory algorithms
- Static-memory-hard functions, and modeling the cost of space vs. time
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- Computational Complexity
- Triangulating a simple polygon in linear time
- On the solution of linear recurrence equations
- Data Mining with optimized two-dimensional association rules
- Visibility Algorithms in the Plane
- Selection and sorting with limited storage
- Optimal shortest path queries in a simple polygon
- Upper bounds for time-space trade-offs in sorting and selection
- Triangulating a simple polygon
- Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
- Constant-work-space algorithms for shortest paths in trees and simple polygons
- Comparison-based time-space lower bounds for selection
- Space-Time Trade-offs for Stack-Based Algorithms
- Title not available (Why is that?)
- Improved upper bounds for time-space tradeoffs for selection with limited storage
- Selection from read-only memory and sorting with minimum data movement
- Multi-pass geometric algorithms
- Corrections to Lee's visibility polygon algorithm
- On the identification of the convex hull of a finite set of points in the plane
- Computing a visibility polygon using few variables
- Implementation and evaluation of decision trees with range and region splitting
- Memory-constrained algorithms for simple polygons
- Linear time algorithm for approximating a curve by a single-peaked curve
- The recognition of deterministic CFLs in small time and space
- On finding the convex hull of a simple polygon
- Title not available (Why is that?)
- Parallel RAMs with owned global memory and deterministic context-free language recognition
- Title not available (Why is that?)
Cited In (16)
- A time-space trade-off for computing the \(k\)-visibility region of a point in a polygon
- Time-space trade-offs for triangulations and Voronoi diagrams
- Time-Space Trade-Off for Finding the k-Visibility Region of a Point in a Polygon
- An applicative random-access stack
- Title not available (Why is that?)
- Frameworks for designing in-place graph algorithms
- Title not available (Why is that?)
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\)
- Space efficient linear time algorithms for BFS, DFS and applications
- A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
- Optimal In-place Algorithms for Basic Graph Problems
- A new balanced subdivision of a simple polygon for time-space trade-off algorithms
- Title not available (Why is that?)
- A Framework for In-place Graph Algorithms
This page was built for publication: Space-time trade-offs for stack-based algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494797)
