About: Lowest common ancestor

(Sponging disallowed)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Lowest common ancestor Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Settlement, 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) (also called least common ancestor) 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).

Attributes	Values
rdf:type	yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects settlement
rdfs:label	Lowest Common Ancestor (de) Ancestro común más bajo (es) Plus petit ancêtre commun (fr) Lowest common ancestor (en) Najniższy wspólny przodek (pl) Наименьший общий предок (ru) Найменший спільний предок (uk) 最近公共祖先 (图论) (zh)
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 (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. (fr) 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. (pl) Наименьший общий предок (нижайший общий предок) вершин u и v в корневом дереве T — наиболее удалённая от корня дерева вершина, лежащая на обоих путях от u и v до корня, т. е. являющаяся предком обеих вершин. Общепринятое сокращение — LCA от англ. lowest (least) common ancestor. (ru) Найменший спільний предок вершин та в кореневому дереві — найбільш віддалена від кореня дерева вершина, яка лежить на обидвох шляхах від та до кореня дерева, тобто є предком обидвох вершин. (uk) 在图论和计算机科学中，最近公共祖先（英語：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。 (zh) 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. (de) 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. (es) In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) 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). (en)
foaf:depiction
dcterms:subject	Trees (graph theory) Theoretical computer science
Wikipage page ID	7196522 (xsd:integer)
Wikipage revision ID	1111669741 (xsd:integer)
Link from a Wikipage to another Wikipage	Euler tour David Eppstein Level ancestor problem Complete binary tree Complex system Object-oriented programming Glossary of graph theory Tree data structure Computer science C (programming language) Trees (graph theory) Tree (graph theory) Distributed computing Heavy path decomposition Lecture Notes in Computer Science Erik Demaine Hasse diagram Graph theory ACM Transactions on Programming Languages and Systems Theoretical computer science Directed acyclic graph Donald Knuth Knowledge Graph Cartesian tree Range minimum query Semilattice Range Minimum Query Tarjan's off-line lowest common ancestors algorithm Inheritance hierarchy Union-find Out-degree
Link from a Wikipage to an external page	https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf http://gim.org.pl/lca/Lowest_Common_Ancestor_Fast_Implementation.html http://hassan-ait-kaci.net/pdf/encoding-toplas-89.pdf http://www.ritambhara.in/lowest-common-ancestor-in-binary-search-tree/ https://archive.org/details/automatalanguage2005inte/page/241 https://archive.org/details/latin2000theoret0000lati/page/88 http://www.cs.sunysb.edu/~bender/pub/JALG05-daglca.pdf http://hackage.haskell.org/package/lca http://uhra.herts.ac.uk/bitstream/2299/12152/2/906535.pdf http://courses.csail.mit.edu/6.851/spring07/scribe/lec16.pdf http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L11/lecture11.pdf http://www.topcoder.com/tc%3Fmodule=Static&d1=tutorials&d2=lowestCommonAncestor http://www.dtic.mil/get-tr-doc/pdf%3FAD=ADA227803%7C https://github.com/networkx/networkx/blob/master/networkx/algorithms/lowest_common_ancestors.py https://web.archive.org/web/20110720050818/http:/stanford-online.stanford.edu/knuth/071203-knuth-300.asx https://web.archive.org/web/20170923151711/http:/www.dtic.mil/get-tr-doc/pdf%3FAD=ADA227803%7C http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search http://www.ics.uci.edu/~eppstein/PADS/LCA.py http://www.math.tau.ac.il/~haimk/papers/lnca-submitted.ps%7C
sameAs	Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor Lowest common ancestor
dbp:wikiPageUsesTemplate	dbt:! dbt:= dbt:About dbt:Citation dbt:Harv

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (61 GB total memory, 49 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software