Two simplified algorithms for maintaining order in a list

Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito

Research output: Chapter in Book/Report/Conference proceedingConference contribution

97 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
EditorsRolf Möhring, Rajeev Raman
PublisherSpringer Verlag
Pages152-164
Number of pages13
ISBN (Electronic)3540441808, 9783540441809
DOIs
StatePublished - 2002
Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
Duration: Sep 17 2002Sep 21 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2461
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th Annual European Symposium on Algorithms, ESA 2002
CountryItaly
CityRome
Period9/17/029/21/02

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Two simplified algorithms for maintaining order in a list'. Together they form a unique fingerprint.

Cite this