Questions tagged [tree]
A tree is a special type of graph which only allows for a hierarchical set of edges similar to a tree . Mathematically it is actually an arborescence. Trees have a root node and children nodes. In formal terms it is described as an acyclic connected graph.
35
questions with no upvoted or accepted answers
13
votes
0
answers
175
views
What is the curve of "search vs. insert"
Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time.
With this ...
- 369
13
votes
0
answers
533
views
Lock-free, constant update-time concurrent tree data-structures?
I've been reading a bit of the literature lately, and have found some rather interesting data-structures.
I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
- 566
13
votes
0
answers
368
views
Applications of an access lemma for dynamic forests?
Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
- 22.9k
7
votes
0
answers
275
views
Number of ordinal trees with n nodes, of depth d, with l leaves
What is the number of ordinal trees (aka rose trees) with $n$ nodes, of depth $d$, with $l$ leaves?
I thought that it was a known results but I could not find it, and neither did the various ...
- 2,723
6
votes
0
answers
341
views
Optimal set union tree
Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
- 679
6
votes
0
answers
196
views
Tree search guided by a probabilistic oracle
I'm trying to find a solution for the following problem.
I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
- 239
5
votes
0
answers
160
views
Complexity of a problem related to Friedman's TREE(k) function?
Background
Given two rooted, vertex-colored trees $T_1, T_2$, $T_1$ is color-preserving inf-embeddle in $T_2$, which we'll denote $T_1 \leq T_2$, if there is an injective $f \colon V(T_1) \to V(T_2)$ ...
- 36.4k
5
votes
0
answers
157
views
Height of AVL tree with random elements
I know that for an AVL tree of N nodes, the depth of the tree is bounded by
$$ \log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$
where $c,b$ are taken from the golden ratio linked to the worst ...
- 171
5
votes
0
answers
161
views
"Context" understanding in tree grammars
The Context-Free tree grammar has rules of the form:
$A\rightarrow t$ or $A(x_1,\dots,x_n)\rightarrow t_x$,
where $A\in N$, $t\in T(N\cup T)$, $t_x\in T(N\cup T\cup \{x_1,\dots,x_n\})$, $T(Z)$ ...
- 635
5
votes
0
answers
316
views
Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$
I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.
I'm now searching for an intuitive, or geometric, or visual proof of ...
- 281
4
votes
0
answers
165
views
What is the exact communication complexity of subtree disjointness?
A classic textbook example for communication complexity is when A and B both receive a subtree of a an $n$-node tree (that they both know), and they need to output whether their subtrees are disjoint ...
- 13.9k
4
votes
0
answers
210
views
Find a pair of nodes with maximum sum of distances in k given trees
For k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ ...
- 235
4
votes
1
answer
1k
views
Given a B-Tree, determine the order keys were inserted
Given a B-tree, determine what order the keys were inserted in. There may be multiple answers: I'd like to generate them all.
Is there any known method for this? Or similar problems?
Clarification:...
- 171
3
votes
0
answers
75
views
Load-balancing; Alternate methods of keeping track of nodes?
Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network.
One popular method uses virtual-...
- 131
2
votes
0
answers
52
views
The number of rooted ordered trees of max-out degree $k$
An ordered tree (also known as ordinal tree and plane tree) is a rooted tree in which the children of each node are ordered. It is known that the number of the ordered tree with $n$ edges is the $n$'...
2
votes
0
answers
66
views
Regular Tree Languages are closed under quotient?
The Wikipedia page for Regular Tree Grammars notes that if $L_1$ and $L_2$ are regular tree languages, than $L_1 \setminus L_2$ is as well. However, it doesn't define this quotient operation for trees,...
- 2,774
2
votes
0
answers
122
views
How to find a merge tree for a set of words?
Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider ...
- 1,292
2
votes
0
answers
225
views
Quadratic Binary Optimization formulation of Steiner Tree problem
can someone point out to me a solution or give advice on how to formulate as efficiently as possible in terms of number of bits the minimum Steiner tree problem as a 0-1 quadratic optimization problem?...
2
votes
0
answers
431
views
Notation for drawing rooted trees with isomorphic subtrees and recursive parts
I need to specify small rooted trees with a lot of repeated parts and some recursive definitions.
To illustrate the need, let's use $s(T_1, T_2, ..., T_k)$ to denote a tree that consists of a degree-$...
- 11.4k
1
vote
0
answers
62
views
Directed tree decompositions on subtrees of DAGs
Given a DAG, is the arboreal decomposition of the DAG with the guarantee that given a node $x$, $v$ such that $x$ is reachable from $v$ are in the subtree of $x$? If not, is there a similar ...
- 23
1
vote
0
answers
101
views
Parallel building time of a k-d tree on n points with n processors
Given a point set with $n$ points to build a k-d tree on. We have $n$ processors available. What is the time-optimal building time for the k-d tree?
A straight forward parallelization would be as ...
- 111
1
vote
0
answers
112
views
Growth of random square lattice trees
Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
- 778
1
vote
0
answers
82
views
Generating random labelled trees
I am looking for a simple rejection-free algorithm to uniformly sample random labelled trees (i.e. to generate each of them with the same probability).
One possibility is to generate Prüfer sequences ...
- 11
1
vote
0
answers
41
views
BK-Tree intersection
I'm looking to calculate the approximate intersection (proximity under a certain distance) of two sets of points in a discrete metric space. In other words, given a metric space $(M, d)$, subsets $A, ...
1
vote
0
answers
276
views
Maximize the weight of MST + sum of vertex weights
I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
- 19
1
vote
0
answers
89
views
Are there any polynomial cases of Balanced Minimum Evolution?
The BME problem has an interest in computational biology, for the reconstruction of phylogenetic trees from a distance matrix. Let me provide some context before defining the problem.
Suppose that we ...
- 314
1
vote
0
answers
58
views
Repartitioning a binary tree
Suppose I have a binary tree $G = (V, E)$ (with undirected edges) that is partitioned into sets of k vertices, where each set of vertices is a connected subgraph of $G$. Additionally, if there are ...
- 383
1
vote
0
answers
246
views
A non-trivial combinatorial optimization
So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be ...
1
vote
0
answers
290
views
How to quantify the tree-like-ness of a graph?
What are good measures of tree-like-ness of a graph and algorithms for calculating them?
- 119
0
votes
0
answers
36
views
Languages for specifying AST transformations with arbitrary arity
I'm developing a "computation assistant": users specify individual steps to take within an algebraic computation and the computer ensures they are applied correctly.
I'm looking for ...
- 259
0
votes
0
answers
62
views
Suffix tree and searching for longest subword that appears two times and two occurencies are not overlapping
I'm learning basics of text algorithms, so my question might seem simple.
Let's have word $S$, i want to find longest subword $x$ such that it appears in $S$ two times and those two occurencies are ...
- 101
0
votes
0
answers
240
views
Steiner Tree and minimum spanning tree
If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
- 11
0
votes
0
answers
75
views
On a property of random rooted trees with $n$ nodes and of height $h$
I am working on a proof that require the result of the following problem:
Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of $...
- 101
-1
votes
1
answer
166
views
Representation suitable for reconstruction of a tree with bounded degree
I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
- 1,281
-4
votes
1
answer
489
views
Distinguish Graph from Tree using Adjacency Matrix
Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle).
For example, given the adjacency matrix:
...
- 1