Notes on the complexity of sorting in abstract machines
Authors:Martti Penttonen and Jyrki Katajainen
Published in:BIT 25,4 (1985), 611-622
Full text:<pdf.gif>PDF (563 kB)  
DOI:10.1007/BF01936140
Copyright:© Springer
Abstract:The complexity of sorting with pointer machines and successor-predecessor random access machines is studied. The size of the problem is defined as the length of the problem string. A linear time algorithm is achieved for sorting by pointer machines. For successor-predecessor random access machines linear time is sufficient in a special case.
Related:<html.gif>HTML (Conference paper)  
BibLATEX:
@article{PK1985J,
  author = {Martti Penttonen and Jyrki Katajainen},
  title = {Notes on the complexity of sorting in abstract machines},
  journaltitle = {BIT},
  volume = {25},
  number = {4},
  year = {1985},
  pages = {611--622},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 31.12.2011.