Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q4312352> ?p ?o }
Showing triples 1 to 55 of
55
with 100 triples per page.
- Q4312352 subject Q7153055.
- Q4312352 subject Q7217255.
- Q4312352 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.".
- Q4312352 thumbnail Lowest_common_ancestor.svg?width=300.
- Q4312352 wikiPageExternalLink lca.
- Q4312352 wikiPageExternalLink lca.ps.
- Q4312352 wikiPageExternalLink S0304397513007226.
- Q4312352 wikiPageExternalLink lec16.pdf.
- Q4312352 wikiPageExternalLink lecture11.pdf.
- Q4312352 wikiPageExternalLink Lowest_Common_Ancestor_Fast_Implementation.html.
- Q4312352 wikiPageExternalLink encoding-toplas-89.pdf.
- Q4312352 wikiPageExternalLink 071203-knuth-300.asx.
- Q4312352 wikiPageExternalLink JALG05-daglca.pdf.
- Q4312352 wikiPageExternalLink LCA.py.
- Q4312352 wikiPageExternalLink lnca-submitted.ps.
- Q4312352 wikiPageExternalLink lowest-common-ancestor-in-binary-search-tree.
- Q4312352 wikiPageExternalLink skewbinary-online-lowest-common-ancestor-search.
- Q4312352 wikiPageExternalLink tc?module=Static&d1=tutorials&d2=lowestCommonAncestor.
- Q4312352 wikiPageExternalLink online-lca.
- Q4312352 wikiPageWikiLink Q1137726.
- Q4312352 wikiPageWikiLink Q1195339.
- Q4312352 wikiPageWikiLink Q1259393.
- Q4312352 wikiPageWikiLink Q131476.
- Q4312352 wikiPageWikiLink Q1501387.
- Q4312352 wikiPageWikiLink Q15777.
- Q4312352 wikiPageWikiLink Q1637549.
- Q4312352 wikiPageWikiLink Q166507.
- Q4312352 wikiPageWikiLink Q17022001.
- Q4312352 wikiPageWikiLink Q17457.
- Q4312352 wikiPageWikiLink Q180634.
- Q4312352 wikiPageWikiLink Q21198.
- Q4312352 wikiPageWikiLink Q212542.
- Q4312352 wikiPageWikiLink Q2130898.
- Q4312352 wikiPageWikiLink Q223655.
- Q4312352 wikiPageWikiLink Q272735.
- Q4312352 wikiPageWikiLink Q3017847.
- Q4312352 wikiPageWikiLink Q324254.
- Q4312352 wikiPageWikiLink Q3531564.
- Q4312352 wikiPageWikiLink Q380172.
- Q4312352 wikiPageWikiLink Q4274653.
- Q4312352 wikiPageWikiLink Q4650737.
- Q4312352 wikiPageWikiLink Q474715.
- Q4312352 wikiPageWikiLink Q4919359.
- Q4312352 wikiPageWikiLink Q5047286.
- Q4312352 wikiPageWikiLink Q624580.
- Q4312352 wikiPageWikiLink Q7153055.
- Q4312352 wikiPageWikiLink Q7217255.
- Q4312352 wikiPageWikiLink Q7661893.
- Q4312352 wikiPageWikiLink Q79872.
- Q4312352 wikiPageWikiLink Q834585.
- Q4312352 wikiPageWikiLink Q854457.
- Q4312352 wikiPageWikiLink Q924044.
- Q4312352 comment "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.".
- Q4312352 label "Lowest common ancestor".
- Q4312352 depiction Lowest_common_ancestor.svg.