Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Lowest_common_ancestor> ?p ?o }
- Lowest_common_ancestor abstract "In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor (Djidjev, Pantziou & Zaroliagis 1991). In ontologies, the lowest common ancestor is also known as the least common subsumer.In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from v and w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity.".
- Lowest_common_ancestor thumbnail Lowest_common_ancestor.svg?width=300.
- Lowest_common_ancestor wikiPageExternalLink lca.
- Lowest_common_ancestor wikiPageExternalLink lca.ps.
- Lowest_common_ancestor wikiPageExternalLink S0304397513007226.
- Lowest_common_ancestor wikiPageExternalLink lec16.pdf.
- Lowest_common_ancestor wikiPageExternalLink lecture11.pdf.
- Lowest_common_ancestor wikiPageExternalLink Lowest_Common_Ancestor_Fast_Implementation.html.
- Lowest_common_ancestor wikiPageExternalLink encoding-toplas-89.pdf.
- Lowest_common_ancestor wikiPageExternalLink 071203-knuth-300.asx.
- Lowest_common_ancestor wikiPageExternalLink JALG05-daglca.pdf.
- Lowest_common_ancestor wikiPageExternalLink LCA.py.
- Lowest_common_ancestor wikiPageExternalLink lnca-submitted.ps.
- Lowest_common_ancestor wikiPageExternalLink lowest-common-ancestor-in-binary-search-tree.
- Lowest_common_ancestor wikiPageExternalLink skewbinary-online-lowest-common-ancestor-search.
- Lowest_common_ancestor wikiPageExternalLink tc?module=Static&d1=tutorials&d2=lowestCommonAncestor.
- Lowest_common_ancestor wikiPageExternalLink online-lca.
- Lowest_common_ancestor wikiPageID "7196522".
- Lowest_common_ancestor wikiPageLength "16972".
- Lowest_common_ancestor wikiPageOutDegree "37".
- Lowest_common_ancestor wikiPageRevisionID "708148221".
- Lowest_common_ancestor wikiPageWikiLink ACM_Transactions_on_Programming_Languages_and_Systems.
- Lowest_common_ancestor wikiPageWikiLink Binary_tree.
- Lowest_common_ancestor wikiPageWikiLink C_(programming_language).
- Lowest_common_ancestor wikiPageWikiLink Cartesian_tree.
- Lowest_common_ancestor wikiPageWikiLink Category:Theoretical_computer_science.
- Lowest_common_ancestor wikiPageWikiLink Category:Trees_(graph_theory).
- Lowest_common_ancestor wikiPageWikiLink Complex_system.
- Lowest_common_ancestor wikiPageWikiLink Computer_science.
- Lowest_common_ancestor wikiPageWikiLink David_Eppstein.
- Lowest_common_ancestor wikiPageWikiLink Directed_acyclic_graph.
- Lowest_common_ancestor wikiPageWikiLink Directed_graph.
- Lowest_common_ancestor wikiPageWikiLink Disjoint-set_data_structure.
- Lowest_common_ancestor wikiPageWikiLink Distributed_computing.
- Lowest_common_ancestor wikiPageWikiLink Donald_Knuth.
- Lowest_common_ancestor wikiPageWikiLink Erik_Demaine.
- Lowest_common_ancestor wikiPageWikiLink Eulerian_path.
- Lowest_common_ancestor wikiPageWikiLink Glossary_of_graph_theory.
- Lowest_common_ancestor wikiPageWikiLink Graph_theory.
- Lowest_common_ancestor wikiPageWikiLink Heavy_path_decomposition.
- Lowest_common_ancestor wikiPageWikiLink Inheritance_(object-oriented_programming).
- Lowest_common_ancestor wikiPageWikiLink Lecture_Notes_in_Computer_Science.
- Lowest_common_ancestor wikiPageWikiLink Level_ancestor_problem.
- Lowest_common_ancestor wikiPageWikiLink Object-oriented_programming.
- Lowest_common_ancestor wikiPageWikiLink Ontology_(information_science).
- Lowest_common_ancestor wikiPageWikiLink Partially_ordered_set.
- Lowest_common_ancestor wikiPageWikiLink Range_minimum_query.
- Lowest_common_ancestor wikiPageWikiLink Reflexive_closure.
- Lowest_common_ancestor wikiPageWikiLink Semilattice.
- Lowest_common_ancestor wikiPageWikiLink Symposium_on_Theory_of_Computing.
- Lowest_common_ancestor wikiPageWikiLink Tarjans_off-line_lowest_common_ancestors_algorithm.
- Lowest_common_ancestor wikiPageWikiLink Transitive_closure.
- Lowest_common_ancestor wikiPageWikiLink Tree_(data_structure).
- Lowest_common_ancestor wikiPageWikiLink Tree_(graph_theory).
- Lowest_common_ancestor wikiPageWikiLink File:Lowest_common_ancestor.svg.
- Lowest_common_ancestor wikiPageWikiLink File:Lowest_common_ancestors_in_a_DAG.svg.
- Lowest_common_ancestor wikiPageWikiLinkText "Lowest common ancestor".
- Lowest_common_ancestor wikiPageWikiLinkText "lowest common ancestor problem".
- Lowest_common_ancestor wikiPageWikiLinkText "lowest common ancestor".
- Lowest_common_ancestor wikiPageWikiLinkText "lowest common subsumer".
- Lowest_common_ancestor author1Link "Alfred Aho".
- Lowest_common_ancestor author2Link "John Hopcroft".
- Lowest_common_ancestor author2Link "Martin Farach-Colton".
- Lowest_common_ancestor author2Link "Robert Tarjan".
- Lowest_common_ancestor author2Link "Uzi Vishkin".
- Lowest_common_ancestor author3Link "Jeffrey Ullman".
- Lowest_common_ancestor first "Alfred".
- Lowest_common_ancestor first "Baruch".
- Lowest_common_ancestor first "Dov".
- Lowest_common_ancestor first "Jeffrey".
- Lowest_common_ancestor first "John".
- Lowest_common_ancestor first "Martin".
- Lowest_common_ancestor first "Michael".
- Lowest_common_ancestor first "Omer".
- Lowest_common_ancestor first "Robert".
- Lowest_common_ancestor first "Uzi".
- Lowest_common_ancestor last "Aho".
- Lowest_common_ancestor last "Bender".
- Lowest_common_ancestor last "Berkman".
- Lowest_common_ancestor last "Farach-Colton".
- Lowest_common_ancestor last "Harel".
- Lowest_common_ancestor last "Hopcroft".
- Lowest_common_ancestor last "Schieber".
- Lowest_common_ancestor last "Tarjan".
- Lowest_common_ancestor last "Ullman".
- Lowest_common_ancestor last "Vishkin".
- Lowest_common_ancestor wikiPageUsesTemplate Template:!.
- Lowest_common_ancestor wikiPageUsesTemplate Template:=.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Citation.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Harv.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Harvs.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Harvtxt.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Math.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Mvar.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Reflist.
- Lowest_common_ancestor wikiPageUsesTemplate Template:Two_other_uses.
- Lowest_common_ancestor year "1973".
- Lowest_common_ancestor year "1984".
- Lowest_common_ancestor year "1988".
- Lowest_common_ancestor year "1993".