| dbo:abstract |
In graph theory and theoretical computer science, the level ancestor problem is the problem of preprocessing a given rooted tree T into a data structure that can determine the ancestor of a given node at a given distance from the root of the tree. More precisely, let T be a rooted tree with n nodes, and let v be an arbitrary node of T. The level ancestor query LA(v,d) requests the ancestor of node v at depth d, where the depth of a node v in a tree is the number of edges on the shortest path from the root of the tree to node v.It is possible to solve this problem in constant time per query, after a preprocessing algorithm that takes O(n) and that builds a data structure that uses O(n) storage space. (en) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/LevelAncestor.png?width=300 |
| dbo:wikiPageID |
35471883 (xsd:integer) |
| dbo:wikiPageLength |
9984 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1062436344 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Method_of_Four_Russians dbr:Euler_tour dbr:Jagged_array dbr:Preprocessor dbr:Range_query_(data_structures) dbr:Lowest_common_ancestor dbr:Shortest_path dbr:Path_(graph_theory) dbr:Theoretical_computer_science dbc:Trees_(graph_theory) dbr:Tree_(data_structure) dbr:Tree_(graph_theory) dbr:Data_structure dbr:Graph_theory dbr:Recursion dbr:Array_data_structure dbc:Theoretical_computer_science dbr:Vertex_(graph_theory) dbr:Precomputation dbr:File:LevelAncestor.png |
| dbp:wikiPageUsesTemplate |
dbt:Radic |
| dct:subject |
dbc:Trees_(graph_theory) dbc:Theoretical_computer_science |
| gold:hypernym |
dbr:Problem |
| rdf:type |
yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects dbo:Disease |
| rdfs:comment |
In graph theory and theoretical computer science, the level ancestor problem is the problem of preprocessing a given rooted tree T into a data structure that can determine the ancestor of a given node at a given distance from the root of the tree. (en) |
| rdfs:label |
Level ancestor problem (en) |
| owl:sameAs |
freebase:Level ancestor problem wikidata:Level ancestor problem dbpedia-th:Level ancestor problem https://global.dbpedia.org/id/3xfKd |
| prov:wasDerivedFrom |
wikipedia-en:Level_ancestor_problem?oldid=1062436344&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/LevelAncestor.png |
| foaf:isPrimaryTopicOf |
wikipedia-en:Level_ancestor_problem |
| is dbo:wikiPageRedirects of |
dbr:Level_Ancestor_Problem |
| is dbo:wikiPageWikiLink of |
dbr:Range_query_(data_structures) dbr:Lowest_common_ancestor dbr:Heavy_path_decomposition dbr:Level_Ancestor_Problem |
| is foaf:primaryTopic of |
wikipedia-en:Level_ancestor_problem |
