Matches in DBpedia 2015-04 for { <http://dbpedia.org/resource/Link/cut_tree> ?p ?o }
Showing triples 1 to 26 of
26
with 100 triples per page.
- cut_tree abstract "A link/cut tree is a type of data structure that can merge (link) and split (cut) data sets in O(log(n)) amortized time, and can find which tree an element belongs to in O(log(n)) amortized time. The overall structure is a forest of trees. Link-Cut trees divide a given represented tree into vertex-disjoint paths, where each path is represented by an auxiliary tree (often splay trees, though the original paper pre-dates splay trees and thus uses biased binary search trees). The nodes in the auxiliary trees are keyed by their depth in the corresponding represented tree. In one variation, Naive Partitioning, the paths are determined by the most recently accessed paths and nodes, similar to Tango Trees. In Partitioning by Size paths are determined by the heaviest child (child with the most children) of the given node. This gives a more complicated structure, but reduces the cost of the operations from amortized O(log n) to worst case O(log n). It has uses in solving a variety of network flow problems and to jive data sets. In the original publication, Sleator and Tarjan referred to link/cut trees as “dynamic trees”, or "dynamic dyno trees".".
- cut_tree thumbnail LinkCutAccess1.png?width=300.
- cut_tree wikiPageExternalLink 07-linkcut.pdf.
- cut_tree wikiPageExternalLink L19.pdf.
- cut_tree wikiPageID "9328337".
- cut_tree wikiPageRevisionID "645748654".
- cut_tree above "Link-Cut Tree".
- cut_tree data Tree.
- cut_tree data "1982".
- cut_tree hasPhotoCollection cut_tree.
- cut_tree header "Time complexity in big O notation".
- cut_tree headerstyle "background:#D6D6F5".
- cut_tree label "Invented by".
- cut_tree label "Invented".
- cut_tree label "Type".
- cut_tree subject Category:Trees_(data_structures).
- cut_tree type Species.
- cut_tree type Thing.
- cut_tree comment "A link/cut tree is a type of data structure that can merge (link) and split (cut) data sets in O(log(n)) amortized time, and can find which tree an element belongs to in O(log(n)) amortized time. The overall structure is a forest of trees. Link-Cut trees divide a given represented tree into vertex-disjoint paths, where each path is represented by an auxiliary tree (often splay trees, though the original paper pre-dates splay trees and thus uses biased binary search trees).".
- cut_tree label "Link/cut tree".
- cut_tree sameAs m.0284rt_.
- cut_tree sameAs Q6554218.
- cut_tree sameAs Q6554218.
- cut_tree wasDerivedFrom cut_tree?oldid=645748654.
- cut_tree depiction LinkCutAccess1.png.
- cut_tree isPrimaryTopicOf cut_tree.
