The Euler tour technique ( ETT ), named after Leonhard Euler , is a method in graph theory for representing trees . The tree is viewed as a directed graph that contains two directed edges for each edge in the tree. The tree can then be represented as a Eulerian circuit of the directed graph, known as the Euler tour representation ( ETR ) of the tree. The ETT allows for efficient, parallel computation of solutions to common problems in algorithmic graph theory . It was introduced by Tarjan and Vishkin in 1984.
11-583: (Redirected from Ett ) [REDACTED] Look up ett in Wiktionary, the free dictionary. Ett or ETT may refer to: Arts [ edit ] Caspar Ett (1788–1847), German composer and organist English Touring Theatre Mathematics [ edit ] Euler tour technique , in graph theory Extensional type theory , in logic Medicine [ edit ] Endotracheal tube , in respiratory medicine Epithelioid trophoblastic tumour ,
22-517: A balanced binary tree with 14 nodes, one for each time each node appears on the tour. We can represent a forest (an acyclic graph) using a collection of ET trees - one ET tree for one forest tree. This representation allows us to quickly answer the question "what is the root of node v?" by just moving to the first node of the ET tree (since nodes in the ET tree are keyed by their location in the Euler tour, and
33-453: A pair of nodes u , v , the first occurrence of either ( u , v ) or ( v , u ) in the ETR is called the advance edge , and the second occurrence is called the retreat edge . This appeals to the intuition that the first time such an edge is traversed the distance to the root is increased, while the second time the distance decreases. Rerooting the tree can be done in constant time O(1) by splitting
44-478: A scientific journal Evacuated Tube Transport Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title ETT . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=ETT&oldid=1198712535 " Category : Disambiguation pages Hidden categories: Short description
55-478: A scientific journal Evacuated Tube Transport Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title ETT . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=ETT&oldid=1198712535 " Category : Disambiguation pages Hidden categories: Short description
66-627: A very rare cancer Ergothioneine transporter , a protein and human gene (SLC22A4) Exercise Tolerance Test , in cardiology Military [ edit ] Embedded Training Teams in Afghanistan EBR ETT , a French armoured personnel carrier Other uses [ edit ] Elementary Teachers of Toronto , a Canadian labour union English Toy Terrier , a dog breed Etruscan language , once spoken in Italy (ISO 639-3: ett) European Transactions on Telecommunications ,
77-504: A very rare cancer Ergothioneine transporter , a protein and human gene (SLC22A4) Exercise Tolerance Test , in cardiology Military [ edit ] Embedded Training Teams in Afghanistan EBR ETT , a French armoured personnel carrier Other uses [ edit ] Elementary Teachers of Toronto , a Canadian labour union English Toy Terrier , a dog breed Etruscan language , once spoken in Italy (ISO 639-3: ett) European Transactions on Telecommunications ,
88-638: Is different from Wikidata All article disambiguation pages All disambiguation pages ett (Redirected from Ett ) [REDACTED] Look up ett in Wiktionary, the free dictionary. Ett or ETT may refer to: Arts [ edit ] Caspar Ett (1788–1847), German composer and organist English Touring Theatre Mathematics [ edit ] Euler tour technique , in graph theory Extensional type theory , in logic Medicine [ edit ] Endotracheal tube , in respiratory medicine Epithelioid trophoblastic tumour ,
99-406: Is different from Wikidata All article disambiguation pages All disambiguation pages Euler tour technique Given an undirected tree presented as a set of edges, the Euler tour representation (ETR) can be constructed in parallel as follows: Construct an edge list (called succ ) in Euler tour order by setting pointers succ( u , v ) for all edges ( u , v ) in parallel according to
110-503: The circular list succ at the new root. All of the following problems can be solved in O(Prefix sum( n )) (the time it takes to solve the prefix sum problem in parallel for a list of n items): Henzinger and King suggest to represent a given tree by keeping its Euler tour in a balanced binary search tree , keyed by the index in the tour. So for example, the unbalanced tree in the example above, having 7 nodes, will be represented by
121-429: The following rule: The resulting list succ will be circular. The overall construction takes work W ( n ) = O(sort( n )) (the time it takes to sort n items in parallel) if the tree has n nodes, as in trees the number of edges is one less than the number of nodes. If the tree has a root, we can split the circular list succ at that root. In that case, we can speak of advance and retreat edges: given
SECTION 10
#1732783361542#541458