Paper by Erik D. Demaine

Reference:

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, “Two Simplified Algorithms for Maintaining Order in a List”, in Proceedings of the 10th Annual European Symposium on Algorithms (ESA 2002), Lecture Notes in Computer Science, volume 2461, Rome, Italy, September 17–21, 2002, pages 152–164.

BibTeX

@InProceedings{DietzSleator_ESA2002,
  AUTHOR        = {Michael A. Bender and Richard Cole and Erik D. Demaine and
                   Martin Farach-Colton and Jack Zito},
  TITLE         = {Two Simplified Algorithms for Maintaining Order in a List},
  BOOKTITLE     = {Proceedings of the 10th Annual European Symposium on
                   Algorithms (ESA 2002)},
  bookurl       = {http://www.dis.uniroma1.it/~algo02/esa02/},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 2461,
  ADDRESS       = {Rome, Italy},
  MONTH         = {September 17--21},
  YEAR          = 2002,
  PAGES         = {152--164},

  COPYRIGHT     = {The paper is \copyright Springer-Verlag.},
  LENGTH        = {12 pages},
  doi           = {https://dx.doi.org/10.1007/3-540-45749-6_17},
  dblp          = {https://dblp.org/rec/conf/esa/BenderCDFZ02},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/3-540-45749-6_17">SpringerLink</A>.},
}

Abstract:

In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions are simple, and we present experimental evidence that suggests that they are superior in practice.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (200k), gzipped PostScript (68k), and PDF (147k).

See information on file formats.

[Google Scholar search]