Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
2018
In the limited-workspace model, we assume that the input of size n lies in a random access read-only memory. The output has to be reported sequentially, and it cannot be accessed or modified. In addition, there is a read-write workspace of O(s) words, where \(s \in \{1, \dots , n\}\) is a given parameter. In a time-space trade-off, we are interested in how the running time of an algorithm improves as s varies from 1 to n.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
34
References
3
Citations
NaN
KQI