List-labeling problem (original) (raw)
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)
| Property | Value |
|---|---|
| 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 | 56041424 (xsd:integer) |
| dbo:wikiPageLength | 15241 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087156667 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Amortized_data_structures dbr:Scapegoat_tree dbr:Persistent_data_structure dbr:Order-maintenance_problem dbr:Cache-oblivious_algorithm dbr:Computer_science dbr:Totally_ordered_set dbr:Weight-balanced_tree dbr:Self-balancing_binary_search_tree dbr:Binary_search_trees dbr:Cache-oblivious_data_structures |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Amortized_data_structures |
| 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 | wikidata:List-labeling problem https://global.dbpedia.org/id/GXu3p |
| prov:wasDerivedFrom | wikipedia-en:List-labeling_problem?oldid=1087156667&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:List-labeling_problem |
| is dbo:wikiPageWikiLink of | dbr:Order-maintenance_problem |
| is foaf:primaryTopic of | wikipedia-en:List-labeling_problem |