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.
109
questions
-1
votes
0
answers
18
views
Capacitated Vehicle Routing- Help in understanding a proof
The paper "A Capacitated Vehicle Routing Problem on a Tree" (https://link.springer.com/content/pdf/10.1007/3-540-49381-6_42.pdf) by Shinya Hamaguchi1 and Naoki Katoh stated in the ...
- 1
0
votes
0
answers
34
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 ...
- 209
4
votes
1
answer
98
views
Complexity of finding a path visiting all leaves on a tree while respecting a distance bound
I am interested in the complexity of a specific variant of the Hamiltonian path problem where we want to visit all leaves of a tree while respecting a distance bound. Formally, given an (undirected, ...
- 8,224
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.3k
2
votes
1
answer
67
views
Spanning Tree that Preserves the Number of Branch Vertices
Suppose a undirected connected graph $G$, denote the number of vertices in $G$ as $n$, number of branch vertices (i.e., vertices with degree $\geq 3$) as $n_{\geq 3}$. Suppose $n_{\geq 3}>\log(n)$.
...
- 77
9
votes
2
answers
366
views
O(n)-space, polylog-time subtree sums in incremental forests?
Consider a forest $G$ of $n$ vertices $v_1, \dots, v_n$ arranged left to right with edges from child to parent always going to the left, i.e. if the parent of vertex $v_i$ is $v_j$, then $j < i$.
...
- 393
2
votes
1
answer
125
views
Is the center of a BFS tree a good approximation of the graphs center?
Given a graph $G=(V,E)$, a center is a vertex $v\in V$ with minimal eccentricity (i.e., $v\in\text{argmin}_v\max_u d(u,v)$).
Finding the center of the graph can easily be done using all-pairs-shortest-...
- 21
4
votes
1
answer
219
views
Binary Trees for Nearest Neighbor Search
Given points $x_1, ..., x_n \in \mathbb{R}^d$, consider a binary decision tree $T$ on $\mathbb{R}^d$ with $L$ leaves, i.e. for a point $y \in \mathbb{R}^d$ at every node of the tree, we check whether $...
- 179
6
votes
1
answer
217
views
Complexity of reachability in directed rooted forests
I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $...
- 133
1
vote
0
answers
57
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
5
votes
0
answers
153
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
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$'...
-4
votes
1
answer
471
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
1
vote
1
answer
72
views
Reachability Query for Tree
What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $...
- 13
3
votes
1
answer
147
views
Notion of "quotient" or "inverse" for recognizable tree languages?
Related to my previous question but this time I have a better idea of what I'm actually asking.
I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, ...
- 2,764
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,764
1
vote
0
answers
100
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
6
votes
0
answers
338
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
4
votes
0
answers
163
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.8k
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 ...
- 748
5
votes
1
answer
97
views
If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?
The homeomorphic embedding relation for trees as I understand it is a well-quasi-order (wqo) on trees when the label of a node determines the number of children of that node, and there are a finite ...
- 605
6
votes
1
answer
165
views
Example of context-free tree language which can not be generated by monadic CFTG
Assuming that a context-free tree language (CFTL) is that which is generated by a context-free tree grammar (CFTG), I am looking for an example of CFTL which can not be generated by a monadic CFTG (...
- 635
7
votes
1
answer
262
views
How fast can we find and disconnect roots in a forest?
Consider a forest of rooted trees. The problem is to support two operations:
disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
findroot(v): find root of the tree ...
4
votes
1
answer
234
views
What are "unranked trees"?
Recently I have some dispute with my colleagues and would like to clarify the following question.
It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each ...
- 635
1
vote
1
answer
86
views
Proving liveness-like property on an infinite tree
(Context: this is a problem from the middle of my dissertation work, abstracted into a more general problem. It's related to showing that some liveness properties hold, so perhaps work from something ...
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
6
votes
2
answers
2k
views
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.
Popular Bloom filter instead of marking just 1 hash ...
- 317
4
votes
0
answers
208
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
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
1
vote
1
answer
154
views
What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?
The only techniques i know are those in the title.
- 195
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
votes
2
answers
156
views
How to continue this algorithm? [closed]
I want to create an algorithm to fill a fixed-size big rectangle (W,H) with the maximum number of fixed-size smaller rectangles (w,h) (I can rotate the small rectangles 90º).
I have thought about ...
- 109
3
votes
2
answers
507
views
Algorithm for computing unordered tree edit distance
I am trying to compute the edit distance between two dendrograms, one produced from hierarchical clustering, and the other manually constructed from some tree structure. In this setting, the rename ...
- 131
4
votes
1
answer
110
views
Place of tree-adjoining grammars in the hierarchy of tree grammars
As tree-adjoining grammars operate with trees, I suppose they can be considered as a kind of tree grammars. If this assumption is correct, I'm wondering: where should we place them in the tree grammar ...
- 635
5
votes
1
answer
144
views
Regarding proper form of production rules of Context-free tree grammars
Is it possible to describe Context-free Tree Grammar $G_t$ such that set of yields of its trees will coincide with Context-sensitive word language $a^nb^nc^n$?
$\{a^nb^nc^n | n>0\}=\{Yield(t)|t\...
- 635
2
votes
1
answer
261
views
Efficient enumeration of the reachable leaves of nodes in a polytree
A polytree is a directed acyclic graph which does not have any undirected cycles, i.e., it is a tree when we replace each directed edge by its undirected counterpart.
Given a polytree $T$ and a node $...
- 8,224
1
vote
0
answers
275
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
7
votes
1
answer
436
views
Minimum Spanning tree on a complete "random" graph
Consider a complete undirected graph with $n$ vertices, $K_n$. Let weight of an edge between vertices $i\; \& \;j$ be a random variable $E_{ij}$. Let $E_{ij} \sim exp(\lambda)$, where $exp(\lambda)...
- 771
7
votes
1
answer
371
views
For a given binary-search tree obtain an isomorphic splay tree
I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en....
- 1,165
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
7
votes
1
answer
391
views
Complexity of "destroying" the graph's minimum spanning tree weight
Assume we have a connected input graph $G=(V,E)$ and a weight function $w:E\to\mathbb N$.
Denote by $w(G)$ the weight of a minimum spanning gree for a graph $G$. For this purpose, define $w(G')$ as $\...
- 9,368
7
votes
0
answers
272
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
2
votes
2
answers
315
views
Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$
Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such ...
- 9,368
7
votes
1
answer
282
views
Inexact labelled binary tree matching
Does anyone recognise the following problems? Do they have names? Are they hard?
If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard ...
- 11.4k
3
votes
5
answers
1k
views
How to constrain a finite automaton (NFA and DFA) to a tree?
I have a finite automaton by the standard model Hopcroft & Ullman define:
$$
M = (Q, \Sigma, \delta, q_0, F)
$$
Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such ...
- 134
10
votes
2
answers
525
views
Exact formula for the number of spanning trees of a rectangle
This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
- 578
6
votes
1
answer
3k
views
How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?
I'm having a difficult time understanding Camerini's algorithm because there are very few clear explanations online. The goal is to find a minimum-bottleneck spanning tree in linear time.
Camerini's ...
- 163
0
votes
0
answers
57
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
237
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
1
vote
1
answer
298
views
Alternating tree automata for arbitrary arity tree
Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees?
More specifically, as an example: let $\Sigma = \{a,b,c\}$ - labels for tree nodes. Trees from $T$ ...
- 635