| Property |
Value |
| dbo:abstract
|
- 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). El ACB de v y w en T es el ancestro compartido de v y w que está localizado más lejos de la raíz. El cómputo del ancestro común más bajo puede ser útil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un árbol: la distancia de v a w puede ser calculada como la distancia desde la raíz hasta v, sumada con la distancia desde la raíz hasta w, menos dos veces la distancia desde la raíz hasta su ancestro común más bajo. En una estructura de datos árbol donde cada nodo referencia a su padre, el ancestro común más bajo puede ser determinado de forma muy simple encontrando la primera intersección de los caminos desde v and w hasta la raíz. En general, el tiempo computacional requerido por este algoritmo es O(h) donde h es la altura del árbol (longitud del camino más largo desde una hoja hasta la raíz). Sin embargo, existen muchos algoritmos para procesar árboles con los que el ancestro común más bajo puede ser encontrado de forma más rápida. Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal. Sin preprocesamiento se puede mejorar el tiempo de cómputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a través del árbol usando skew-binary random access lists, premitiendo aún al árbol ser extendido en tiempo constante (Edward Kmett (2012)). (es)
- 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). El ACB de v y w en T es el ancestro compartido de v y w que está localizado más lejos de la raíz. El cómputo del ancestro común más bajo puede ser útil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un árbol: la distancia de v a w puede ser calculada como la distancia desde la raíz hasta v, sumada con la distancia desde la raíz hasta w, menos dos veces la distancia desde la raíz hasta su ancestro común más bajo. En una estructura de datos árbol donde cada nodo referencia a su padre, el ancestro común más bajo puede ser determinado de forma muy simple encontrando la primera intersección de los caminos desde v and w hasta la raíz. En general, el tiempo computacional requerido por este algoritmo es O(h) donde h es la altura del árbol (longitud del camino más largo desde una hoja hasta la raíz). Sin embargo, existen muchos algoritmos para procesar árboles con los que el ancestro común más bajo puede ser encontrado de forma más rápida. Se puede buscar en tiempo constante por pregunta después de un preprocesamiento en tiempo lineal. Sin preprocesamiento se puede mejorar el tiempo de cómputo del algoritmo ingenuo hasta O(log h) almacenando los caminos a través del árbol usando skew-binary random access lists, premitiendo aún al árbol ser extendido en tiempo constante (Edward Kmett (2012)). (es)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:author1Link
|
- Alfred Aho (es)
- Alfred Aho (es)
|
| prop-es:author2Link
|
- Jon Bentley (es)
- John Hopcroft (es)
- Robert Tarjan (es)
- Uzi Vishkin (es)
- Jon Bentley (es)
- John Hopcroft (es)
- Robert Tarjan (es)
- Uzi Vishkin (es)
|
| prop-es:author3Link
|
- Jeffrey Ullman (es)
- Robert Tarjan (es)
- Jeffrey Ullman (es)
- Robert Tarjan (es)
|
| prop-es:contribution
|
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE (es)
- On finding lowest common ancestors in trees (es)
- The LCA problem revisited (es)
- Scaling and related techniques for geometry problems (es)
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE (es)
- On finding lowest common ancestors in trees (es)
- The LCA problem revisited (es)
- Scaling and related techniques for geometry problems (es)
|
| prop-es:date
| |
| prop-es:doi
|
- 101007 (xsd:integer)
- 101137 (xsd:integer)
- 101145 (xsd:integer)
|
| prop-es:first
|
- Uzi (es)
- John (es)
- Martin (es)
- Stephen (es)
- Jeffrey (es)
- Baruch (es)
- Alfred (es)
- Omer (es)
- Johannes (es)
- Cyril (es)
- Haim (es)
- Michael A. (es)
- Robert E. (es)
- Dov (es)
- Harold N. (es)
- Jon Louis (es)
- Theis (es)
- Volker (es)
- Uzi (es)
- John (es)
- Martin (es)
- Stephen (es)
- Jeffrey (es)
- Baruch (es)
- Alfred (es)
- Omer (es)
- Johannes (es)
- Cyril (es)
- Haim (es)
- Michael A. (es)
- Robert E. (es)
- Dov (es)
- Harold N. (es)
- Jon Louis (es)
- Theis (es)
- Volker (es)
|
| prop-es:issue
|
- 2 (xsd:integer)
- 3 (xsd:integer)
- 6 (xsd:integer)
|
| prop-es:journal
|
- SIAM Journal on Computing (es)
- Theory of Computing Systems (es)
- SIAM Journal on Computing (es)
- Theory of Computing Systems (es)
|
| prop-es:last
|
- Bentley (es)
- Ullman (es)
- Fischer (es)
- Tarjan (es)
- Aho (es)
- Bender (es)
- Kaplan (es)
- Gabow (es)
- Harel (es)
- Alstrup (es)
- Berkman (es)
- Farach-Colton (es)
- Gavoille (es)
- Heun (es)
- Hopcroft (es)
- Rauhe (es)
- Schieber (es)
- Vishkin (es)
- Bentley (es)
- Ullman (es)
- Fischer (es)
- Tarjan (es)
- Aho (es)
- Bender (es)
- Kaplan (es)
- Gabow (es)
- Harel (es)
- Alstrup (es)
- Berkman (es)
- Farach-Colton (es)
- Gavoille (es)
- Heun (es)
- Hopcroft (es)
- Rauhe (es)
- Schieber (es)
- Vishkin (es)
|
| prop-es:location
|
- New York, NY, USA (es)
- New York, NY, USA (es)
|
| prop-es:pages
|
- 36 (xsd:integer)
- 88 (xsd:integer)
- 135 (xsd:integer)
- 221 (xsd:integer)
- 253 (xsd:integer)
- 338 (xsd:integer)
- 441 (xsd:integer)
- 1253 (xsd:integer)
|
| prop-es:publisher
|
- Springer-Verlag (es)
- ACM (es)
- Springer-Verlag (es)
- ACM (es)
|
| prop-es:series
|
- Lecture Notes in Computer Science (es)
- Lecture Notes in Computer Science (es)
|
| prop-es:title
|
- dbpedia-es:Symposium_on_Theory_of_Computing
- Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching (es)
- Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment (es)
- On finding lowest common ancestors: simplification and parallelization (es)
- Recursive Star-Tree Parallel Data Structure (es)
- Fast algorithms for finding nearest common ancestors (es)
- Proceedings of the 4th Latin American Symposium on Theoretical Informatics (es)
|
| prop-es:url
| |
| prop-es:volume
|
- 13 (xsd:integer)
- 17 (xsd:integer)
- 22 (xsd:integer)
- 37 (xsd:integer)
- 1776 (xsd:integer)
- 4009 (xsd:integer)
|
| prop-es:year
|
- 1973 (xsd:integer)
- 1984 (xsd:integer)
- 1988 (xsd:integer)
- 1993 (xsd:integer)
- 2004 (xsd:integer)
- 2006 (xsd:integer)
|
| dct:subject
| |
| rdfs:comment
|
- 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)
- 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)
|
| rdfs:label
|
- Ancestro común más bajo (es)
- Ancestro común más bajo (es)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
