Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Two Simplified Algorithms for Maintaining Order in a List
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 2461/2002 |
| Book | Algorithms — ESA 2002 |
| DOI | 10.1007/3-540-45749-6 |
| Copyright | 2002 |
| ISBN | 978-3-540-44180-9 |
| DOI | 10.1007/3-540-45749-6_17 |
| Pages | 219-223 |
| Subject Collection | Computer Science |
| SpringerLink Date | Tuesday, January 01, 2002 |
| |
|
Two Simplified Algorithms for Maintaining Order in a List
Michael A. Bender6  , Richard Cole7 , Erik D. Demaine8 , Martin Farach-Colton9, 10 and Jack Zito6
| (6) |
Dept of Computer Science, SUNY Stony Brook, Stony Brook, 11794 NY, USA |
| (7) |
Courant Institute, New York University, 251 Mercer Street, 10012 New York, NY, USA |
| (8) |
MIT Laboratory for Computer Science, 200 Technology Square, 02139 Cambridge, MA, USA |
| (9) |
Google Inc., 2400 Bayshore Parkway, 94043 Mountain View, CA, USA |
| (10) |
Department of Computer Science, Rutgers University, 08855 Piscataway, NJ, USA |
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.
Supported in part by NSF Grants CCR-9800085 and CCR-0105678.
Supported in part by NSF Grant EIA-0112849.
Supported in part by NSF Grant CCR-9820879.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|