Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Link/cut_tree> ?p ?o }
Showing triples 1 to 75 of
75
with 100 triples per page.
- cut_tree abstract "A link/cut tree is a data structure for representing a forest (= set of trees).Our ultimate goal is: given a certain node in the forest, find the root of the tree it belongs to (in order to check whether two nodes belong to the same tree). The represented forest is given and it might be unbalanced, so if we represent the forest as a plain collection of its trees, it might take us a long time to find the root of a given node.However, if we represent each tree in the forest as a link/cut tree, we can find which tree an element belongs to in O(log(n)) amortized time. Moreover, we can quickly adjust the collection of link/cut trees to changes in the represented forest. In particular, we can adjust it to merge (link) and split (cut) in O(log(n)) amortized time.Link-Cut trees divide each tree in the represented forest 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 wikiPageExternalLink dynamic-trees.pdf.
- cut_tree wikiPageExternalLink self-adjusting.pdf.
- cut_tree wikiPageID "9328337".
- cut_tree wikiPageLength "15377".
- cut_tree wikiPageOutDegree "28".
- cut_tree wikiPageRevisionID "682770690".
- cut_tree wikiPageWikiLink Amortized_analysis.
- cut_tree wikiPageWikiLink Big_O_notation.
- cut_tree wikiPageWikiLink Category:Trees_(data_structures).
- cut_tree wikiPageWikiLink Daniel_Dominic_Sleator.
- cut_tree wikiPageWikiLink Daniel_Sleator.
- cut_tree wikiPageWikiLink Data_structure.
- cut_tree wikiPageWikiLink Dinics_algorithm.
- cut_tree wikiPageWikiLink Dynamic_connectivity.
- cut_tree wikiPageWikiLink Euler_tour_technique.
- cut_tree wikiPageWikiLink Euler_tour_tree.
- cut_tree wikiPageWikiLink Forest_(graph_theory).
- cut_tree wikiPageWikiLink Journal_of_the_ACM.
- cut_tree wikiPageWikiLink Logarithm.
- cut_tree wikiPageWikiLink Maximum_flow_problem.
- cut_tree wikiPageWikiLink Potential_method.
- cut_tree wikiPageWikiLink Robert_Endre_Tarjan.
- cut_tree wikiPageWikiLink Robert_Tarjan.
- cut_tree wikiPageWikiLink Splay_tree.
- cut_tree wikiPageWikiLink Splay_trees.
- cut_tree wikiPageWikiLink Tango_Trees.
- cut_tree wikiPageWikiLink Tango_tree.
- cut_tree wikiPageWikiLink Time_complexity.
- cut_tree wikiPageWikiLink Tree.
- cut_tree wikiPageWikiLink Tree_(graph_theory).
- cut_tree wikiPageWikiLink File:LinkCutAccess1.png.
- cut_tree wikiPageWikiLink File:LinkCutAccess2.png.
- cut_tree wikiPageWikiLink File:Linkcuttree1.png.
- cut_tree wikiPageWikiLink File:Pseudo-code.png.
- cut_tree wikiPageWikiLinkText "Link/cut tree".
- cut_tree wikiPageWikiLinkText "link/cut tree".
- cut_tree above "Link-Cut Tree".
- cut_tree data Daniel_Dominic_Sleator.
- cut_tree data Daniel_Sleator.
- cut_tree data Robert_Endre_Tarjan.
- cut_tree data Robert_Tarjan.
- 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 wikiPageUsesTemplate Template:CS-Trees.
- cut_tree wikiPageUsesTemplate Template:Cite_book.
- cut_tree wikiPageUsesTemplate Template:Cite_journal.
- cut_tree wikiPageUsesTemplate Template:Frac.
- cut_tree wikiPageUsesTemplate Template:Infobox.
- cut_tree wikiPageUsesTemplate Template:Main.
- cut_tree wikiPageUsesTemplate Template:Refbegin.
- cut_tree wikiPageUsesTemplate Template:Refend.
- cut_tree wikiPageUsesTemplate Template:Use_dmy_dates.
- cut_tree subject Category:Trees_(data_structures).
- cut_tree hypernym Structure.
- cut_tree type Building.
- cut_tree type Structure.
- cut_tree type Technique.
- cut_tree comment "A link/cut tree is a data structure for representing a forest (= set of trees).Our ultimate goal is: given a certain node in the forest, find the root of the tree it belongs to (in order to check whether two nodes belong to the same tree).".
- 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=682770690.
- cut_tree depiction LinkCutAccess1.png.
- cut_tree isPrimaryTopicOf cut_tree.