| dbo:abstract
|
- In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations:
* insert(X, Y), which inserts X immediately after Y in the total order;
* order(X, Y), which determines if X precedes Y in the total order; and
* delete(X), which removes X from the set. Paul Dietz first introduced a data structure to solve this problem in1982. This datastructure supports insert(X, Y) in (in Big O notation)amortized time and order(X, Y) in constant time but doesnot support deletion. Athanasios Tsakalidis used BB[α] trees with the same performance bounds that supportsdeletion in and improved insertion and deletion performance to amortized time with indirection. Dietz and Daniel Sleator published an improvement to worst-case constant time in 1987. Michael Bender, Richard Cole and Jack Zito published significantly simplified alternatives in 2004. Bender, Fineman, Gilbert, Kopelowitz and Montes also published a deamortized solution in 2017. Efficient data structures for order-maintenance have applications inmany areas, including data structure persistence, graph algorithms and fault-tolerant data structures. (en)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 12043 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations:
* insert(X, Y), which inserts X immediately after Y in the total order;
* order(X, Y), which determines if X precedes Y in the total order; and
* delete(X), which removes X from the set. Efficient data structures for order-maintenance have applications inmany areas, including data structure persistence, graph algorithms and fault-tolerant data structures. (en)
|
| rdfs:label
|
- Order-maintenance problem (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
