About: Lowest common ancestor     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatGraphTheoryObjects, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FLowest_common_ancestor

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) T 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).

AttributesValues
rdf:type
rdfs:label
  • Lowest Common Ancestor
  • Lowest common ancestor
  • Ancestro común más bajo
  • Plus petit ancêtre commun
  • Najniższy wspólny przodek
  • Наименьший общий предок
  • Найменший спільний предок
  • 最近公共祖先 (图论)
rdfs:comment
  • En théorie des graphes, le plus petit ancêtre commun de deux nœuds d'un arbre est le nœud le plus bas dans l'arbre (ie le plus profond) ayant ces deux nœuds pour descendants. Le terme en anglais est Lowest Common Ancestor (LCA). Les expressions premier ancêtre commun et plus proche ancêtre commun sont aussi utilisées. Divers algorithmes ont été inventés pour trouver rapidement le plus petit ancêtre commun.
  • Najniższy wspólny przodek (ang. lowest common ancestor, LCA) – najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy.
  • Наименьший общий предок (нижайший общий предок) вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обеих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor.
  • 在图论和计算机科学中,最近公共祖先(英語:lowest common ancestor)是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里,我们定义一个节点也是其自己的后代,因此如果v是w的后代,那么w就是v和w的最近公共祖先。 最近公共祖先是两个节点所有公共祖先中离根节点最远的,计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离,可以使用以下方法:分别计算由v到根节点和w到根节点的距离,两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。
  • Найменший спільний предок вершин та в кореневому дереві — найбільш віддалена від кореня дерева вершина, яка лежить на обидвох шляхах від та до кореня дерева, тобто є предком обидвох вершин.
  • Als Lowest Common Ancestor (LCA) oder „letzter gemeinsamer Vorfahre“ wird in der Informatik und Graphentheorie ein Ermittlungskonzept bezeichnet, das einen gegebenen gewurzelten Baum von Datenstrukturen effizient vorverarbeitet, sodass anschließend Anfragen nach dem letzten gemeinsamen Vorfahren für beliebige Knotenpaare in konstanter Zeit beantwortet werden können.
  • 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) T 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).
  • El ancestro común más bajo (ACB) es un concepto dentro de la Teoría de grafos y Ciencias de la computación. Sea T un árbol con raíz y n nodos. El ancestro común más bajo entre dos nodos v y w se define como el nodo más bajo en T que tiene a v y w como descendientes (donde se permite a un nodo ser descendiente de él mismo). Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal.
foaf:depiction
  • External Image
foaf:isPrimaryTopicOf
thumbnail
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
sameAs
dbp:wikiPageUsesTemplate
first
  • John
  • Martin
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3319 as of Dec 29 2020, on Linux (x86_64-centos_6-linux-glibc2.12), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software