| dbo:abstract
|
- In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T. It is named after Robert Tarjan, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant time per operation when the number of pairs of nodes is similar in magnitude to the number of nodes. A later refinement by speeds the algorithm up to linear time. (en)
- In informatica, l'algoritmo di Tarjan del più basso antenato comune offline è un algoritmo per il calcolo del per una coppia di nodi in un albero, basata sulla struttura dati union-find. Il più basso antenato comune di due nodi d ed e in un albero T è il nodo g antenato sia di d che di e che possiede la profondità maggiore in T. L'algoritmo prende il nome da Robert Tarjan, che sviluppò la tecnica nel 1979. Quello di Tarjan è un algoritmo offline; ovvero, a differenza degli altri algoritmi del più basso antenato comune, richiede di specificare in anticipo tutte le coppie di nodi per cui si vuole individuare il più basso antenato comune. La versione più semplice dell'algoritmo utilizza la struttura dati union-find che, a differenza delle strutture dati usate in altri algoritmi per il più basso antenato comune, può richiedere più di tempo costante per ogni operazione quando il numero delle paia di nodi ha un ordine di grandezza simile a quello dei nodi. Una modifica successiva di Gaboow e Tarjan velocizza l'algoritmo ad un tempo lineare. (it)
- Algorytm offline Tarjana znajdowania najniższego wspólnego przodka – algorytm obliczający najniższego wspólnego przodka dla pary węzłów w drzewie, bazujący na strukturze zbiorów rozłącznych. 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. Algorytm nosi nazwę Roberta Tarjana, który wymyślił tę technikę w 1979 roku. Algorytm Tarjana zaliczany jest do klasy algorytmów offline, co oznacza, że w przeciwieństwie do innych algorytmów wyznaczania przodka, wymaga podania przed rozpoczęciem działania wszystkich par wierzchołków dla których będzie obliczany najniższy wspólny przodek. Najprostsza wersja algorytmu używająca struktury "find union", w przeciwieństwie do innych algorytmów wyszukiwania wspólnego przodka może nie działać w stałym czasie dla każdej operacji, gdy liczba par wierzchołków jest bliska liczbie wierzchołków w drzewie. Ostatnie poprawki przyspieszają czas działania algorytmu do liniowego. (pl)
- Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка — алгоритм для знаходження найменшого спільного предка пари вузлів у дереві. Він названий на честь Роберта Андре Тарджана, який відкрив цей алгоритм у 1979 році. Алгоритм Тарджана не є алгоритмом реального часу, тобто, він вимагає, щоб усі пари вузлів, для яких потрібно знайти найменший спільний предок, були вказані заздалегідь. (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4307 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка — алгоритм для знаходження найменшого спільного предка пари вузлів у дереві. Він названий на честь Роберта Андре Тарджана, який відкрив цей алгоритм у 1979 році. Алгоритм Тарджана не є алгоритмом реального часу, тобто, він вимагає, щоб усі пари вузлів, для яких потрібно знайти найменший спільний предок, були вказані заздалегідь. (uk)
- In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T. It is named after Robert Tarjan, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant ti (en)
- In informatica, l'algoritmo di Tarjan del più basso antenato comune offline è un algoritmo per il calcolo del per una coppia di nodi in un albero, basata sulla struttura dati union-find. Il più basso antenato comune di due nodi d ed e in un albero T è il nodo g antenato sia di d che di e che possiede la profondità maggiore in T. L'algoritmo prende il nome da Robert Tarjan, che sviluppò la tecnica nel 1979. Quello di Tarjan è un algoritmo offline; ovvero, a differenza degli altri algoritmi del più basso antenato comune, richiede di specificare in anticipo tutte le coppie di nodi per cui si vuole individuare il più basso antenato comune. La versione più semplice dell'algoritmo utilizza la struttura dati union-find che, a differenza delle strutture dati usate in altri algoritmi per il più ba (it)
- Algorytm offline Tarjana znajdowania najniższego wspólnego przodka – algorytm obliczający najniższego wspólnego przodka dla pary węzłów w drzewie, bazujący na strukturze zbiorów rozłącznych. 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. Algorytm nosi nazwę Roberta Tarjana, który wymyślił tę technikę w 1979 roku. Algorytm Tarjana zaliczany jest do klasy algorytmów offline, co oznacza, że w przeciwieństwie do innych algorytmów wyznaczania przodka, wymaga podania przed rozpoczęciem działania wszystkich par wierzchołków dla których będzie obliczany najniższy wspólny przodek. (pl)
|
| rdfs:label
|
- Algoritmo di Tarjan del più basso antenato comune offline (it)
- Algorytm Tarjana znajdowania najniższego wspólnego przodka (pl)
- Tarjan's off-line lowest common ancestors algorithm (en)
- Офлайновий алгоритм Тарджана для пошуку найменшого спільного предка (uk)
|
| owl:differentFrom
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
