Stable minimum space partitioning in linear time: Errata
Authors:Jyrki Katajainen and Tomi Pasanen
Publication:Web document (2014)
Errata:
Abstract, last sentence:
multisets → sets
Theorem 3:
This theorem is weak since the contant α in the n log2 n term may be larger than the constant 1 in the ∑i=1k ni log2 ni term. The result is only meaningful for sets, not for multisets. We managed to provide a sorting algorithm that is stable, runs in minimum space, and has optimal running time for multisets in our 1994 paper "Sorting multisets stably in minimum space" (Acta Informatica 31,4 (1994), 301–313).
Related:<html.gif>HTML (Journal article)  
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.08.2014.