| dbo:abstract
|
- In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:
* insert(X), which inserts X into set S;
* delete(X), which removes X from set S;
* label(X), which returns a label assigned to X subject to:
* label(X)
* X,Y S, X < Y implies label(X) < label(Y) The cost of a list labeling algorithm is the number of label (re-)assignments per insertion or deletion. List labeling algorithms have applications in many areas, including the order-maintenance problem, , data structure persistence, graph algorithms and fault-tolerant data structures. Sometimes the list labeling problem is presented where S is not a set of values but rather a set of objects subject to a total order. In this setting, when an item is inserted into S, it is specified to be the successor of some other item already in S. For example, this is the way that list labeling is used in the order-maintenance problem. The solutions presented below apply to both formulations. (en)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 15241 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:
* insert(X), which inserts X into set S;
* delete(X), which removes X from set S;
* label(X), which returns a label assigned to X subject to:
* label(X)
* X,Y S, X < Y implies label(X) < label(Y) (en)
|
| rdfs:label
|
- List-labeling problem (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
