<p>Chapter 5.1 in "Data Structures and Network Algorithms", which is ref. 43 in the paper you cited, seems like it might have the answer:</p>

<p><a href="http://books.google.com/books?id=JiC7mIqg-X4C&amp;lpg=PP1&amp;ots=8frbjj8vL0&amp;dq=data%20structures%20and%20network%20algorithms&amp;pg=PA59#v=onepage&amp;q&amp;f=false" rel="nofollow">http://books.google.com/books?id=JiC7mIqg-X4C&amp;lpg=PP1&amp;ots=8frbjj8vL0&amp;dq=data%20structures%20and%20network%20algorithms&amp;pg=PA59#v=onepage&amp;q&amp;f=false</a></p>

<blockquote>
  <p>...In discussing this problem we shall use 'm' to denote the number of operations and 'n' to denote the numebr of vertices (maketree operations).  One way to solve this problem is to store with each vertex its parent and its cost.  With this representation each maketree, link, or cut operation takes O(1) time, and each findroot, findcost, or addcost operation takes time proportiatonl to the depth of the input vertex, which is O(n)...</p>
</blockquote>

<p>Several more successive pages are available in the preview.</p>

CC BY-SA 2.5
2010-11-24T14:37:50.683Z
This chapter is pretty much similar to the link-cut tree paper itself; see the last three paragraph in p.365 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.9150&rep=rep1&type=pdf
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-24T14:40:58.483Z
Since later in the algorithm the operations which cost $O(n)$ are essential, this naive implementation can not be used. I'm looking for the main implementation introduced in the same paper, which have a time bound $O(\log n)$ for each operation.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-24T22:59:15.107Z
i was unable to find any other information to backup this claim, so i think they must either be, a. referring to this 'naive' construction (perhaps mistakenly), b. referring to the 'make_tree' operation which simply initializes a new one-node tree, or perhaps c. conflating the two.  otherwise, barring additional evidence i'm inclined to think that you are correct.
s8soj3o289
CC BY-SA 2.5
2010-11-24T13:58:22.747Z
2010-11-24T13:58:22.747Z
s8soj3o289
<p>Many thanks to <a href="http://www.csie.ntu.edu.tw/~hil/">Hsueh-I Lu</a>, my teacher in National Taiwan University, who provides the following solution.</p>

<p>It turns out that the answer is rather simple; in the initialization of a data structure, <strong>we don't have to construct the structure by the queries and operations it supports</strong>. Of course, we cannot perform queries during the construction like we usually do if we build the tree by <em>link</em> operation; but in this separator decomposition application we don't need it.</p>

<p>That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by <em>link</em> operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.</p>

<p>For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.</p>

CC BY-SA 2.5
2011-01-17T02:04:26.987Z
2011-01-17T02:04:26.987Z
Hsien-Chih Chang 張顯之
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.9150&amp;rep=rep1&amp;type=pdf"><strong>Link-cut tree</strong></a> is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation <em>link</em> combines two trees in the forest into one, while operation <em>cut</em> divide a tree in the forest into two trees.) </p>

<p>Several applications are known by using link-cut trees, and here I'm particularly interested in Goodrich's <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.169&amp;rep=rep1&amp;type=pdf"><strong>separator decomposition</strong></a>, which given a $n$-node plane graph $G$ one can obtain a corresponding binary tree where nodes are subgraphs of $G$, and the children of a node $H$ are the subgraphs of $H$ divided by the separator on $H$. Such a decomposition can be easily constructed in $O(n \log n)$ time (since a separator can be found in $O(n)$ time, and since the separator divides the graph so balanced, after $O(\log n)$ level of separations the leaves of the tree are of size $O(1)$). The main contribution of Goodrich is that he can construct such a decomposition in time $O(n)$, by maintaining and reusing the data structures used for finding separators in each level.</p>

<p>One of the data structures being used in the construction, is indeed the link-cut tree. In page 7 of the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.169&amp;rep=rep1&amp;type=pdf">paper</a> by Goodrich, he claimed that the initialization of the link-cut tree can be done in time $O(n)$. While I go through all the papers cited there, it seems to me that if we construct a link-cut tree via operation <em>link</em>, it takes time $O(n \log n)$ in total.</p>

<blockquote>
  <p>Do I misunderstand something? Can the initialization of a link-cut tree be done in time $O(n)$? </p>
</blockquote>

<ds.algorithms><ds.data-structures><time-complexity><tree><dynamic-algorithms>
What is the initialization time of a link-cut tree?
Hsien-Chih Chang 張顯之
# What is the initialization time of a link-cut tree?

(Asked by: username_0 on 2010-11-24)

[**Link-cut tree**](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.9150&rep=rep1&type=pdf) is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation *link* combines two trees in the forest into one, while operation *cut* divide a tree in the forest into two trees.)

Several applications are known by using link-cut trees, and here I'm particularly interested in Goodrich's [**separator decomposition**](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.169&rep=rep1&type=pdf), which given a $n$-node plane graph $G$ one can obtain a corresponding binary tree where nodes are subgraphs of $G$, and the children of a node $H$ are the subgraphs of $H$ divided by the separator on $H$. Such a decomposition can be easily constructed in $O(n \log n)$ time (since a separator can be found in $O(n)$ time, and since the separator divides the graph so balanced, after $O(\log n)$ level of separations the leaves of the tree are of size $O(1)$). The main contribution of Goodrich is that he can construct such a decomposition in time $O(n)$, by maintaining and reusing the data structures used for finding separators in each level.

One of the data structures being used in the construction, is indeed the link-cut tree. In page 7 of the [paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.169&rep=rep1&type=pdf) by Goodrich, he claimed that the initialization of the link-cut tree can be done in time $O(n)$. While I go through all the papers cited there, it seems to me that if we construct a link-cut tree via operation *link*, it takes time $O(n \log n)$ in total.

> Do I misunderstand something? Can the initialization of a link-cut tree be done in time $O(n)$?

**Tags:** ds.algorithms, ds.data-structures, time-complexity, tree, dynamic-algorithms


---

## 2 answers

### Answer by username_0 on 2011-01-17. Score: 6 | Accepted answer

Many thanks to [Hsueh-I Lu](http://www.csie.ntu.edu.tw/~hil/), my teacher in National Taiwan University, who provides the following solution.

It turns out that the answer is rather simple; in the initialization of a data structure, **we don't have to construct the structure by the queries and operations it supports**. Of course, we cannot perform queries during the construction like we usually do if we build the tree by *link* operation; but in this separator decomposition application we don't need it.

That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by *link* operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.

For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.


---

### Answer by username_1 on 2010-11-24. Score: 0

Chapter 5.1 in "Data Structures and Network Algorithms", which is ref. 43 in the paper you cited, seems like it might have the answer:

<http://books.google.com/books?id=JiC7mIqg-X4C&lpg=PP1&ots=8frbjj8vL0&dq=data%20structures%20and%20network%20algorithms&pg=PA59#v=onepage&q&f=false>

> ...In discussing this problem we shall use 'm' to denote the number of operations and 'n' to denote the numebr of vertices (maketree operations). One way to solve this problem is to store with each vertex its parent and its cost. With this representation each maketree, link, or cut operation takes O(1) time, and each findroot, findcost, or addcost operation takes time proportiatonl to the depth of the input vertex, which is O(n)...

Several more successive pages are available in the preview.

> **Comments:**
> **username_0**: This chapter is pretty much similar to the link-cut tree paper itself; see the last three paragraph in p.365 of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.9150&rep=rep1&type=pdf  
> **username_0**: Since later in the algorithm the operations which cost $O(n)$ are essential, this naive implementation can not be used. I'm looking for the main implementation introduced in the same paper, which have a time bound $O(\log n)$ for each operation.  
> **username_1**: i was unable to find any other information to backup this claim, so i think they must either be, a. referring to this 'naive' construction (perhaps mistakenly), b. referring to the 'make_tree' operation which simply initializes a new one-node tree, or perhaps c. conflating the two.  otherwise, barring additional evidence i'm inclined to think that you are correct.  

---

