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.

Filter by
Sorted by
Tagged with
-1
votes
0answers
47 views

Total number of trees where non-leaf nodes have at least 2 children

Given $N$ leaves, how many trees can be constructed if every non-leaf node has at least 2 children? Below are the 30 trees given $N=5$: Additionally, if we account for the order of $X_1,X_2,X_3,X_4,...
2
votes
0answers
95 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
votes
0answers
48 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,...
1
vote
0answers
93 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 ...
6
votes
0answers
148 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 ...
4
votes
0answers
138 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 ...
1
vote
0answers
100 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 ...
5
votes
1answer
79 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 ...
6
votes
1answer
130 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 (...
7
votes
1answer
219 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
1answer
101 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 ...
1
vote
1answer
75 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
0answers
57 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 ...
4
votes
1answer
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 ...
3
votes
0answers
89 views

Looking for a specific tree automata model

is there any tree automata model over unranked trees (that is with unbounded number of children for each node), such that: Checking non-emptiness and universality is decidable in elementary time, ...
4
votes
0answers
181 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)$ ...
5
votes
0answers
160 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)$ ...
1
vote
1answer
130 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.
1
vote
0answers
36 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
2answers
123 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 ...
2
votes
1answer
252 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 ...
3
votes
1answer
100 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 ...
5
votes
1answer
134 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\...
2
votes
1answer
170 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 $...
1
vote
0answers
174 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 ...
7
votes
1answer
289 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)...
6
votes
1answer
252 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....
12
votes
0answers
165 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 ...
7
votes
1answer
354 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 $\...
7
votes
0answers
247 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
votes
2answers
286 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 ...
7
votes
1answer
258 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 ...
3
votes
5answers
780 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 ...
10
votes
2answers
290 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 ...
6
votes
1answer
2k 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 ...
0
votes
0answers
43 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 ...
0
votes
0answers
220 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 ...
1
vote
1answer
230 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$ ...
3
votes
1answer
255 views

Graph (Forest) representation that supports edge deletion and efficient traversal

I am trying to write a data structure that given a general tree (or forest) will support the following operations: Edge deletion Connected(u,v) queries This problem is addressed in section two of ...
7
votes
2answers
4k views

How can I find the second cheapest spanning tree?

The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead. Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly ...
0
votes
0answers
65 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 $...
0
votes
2answers
672 views

Pre order traversal of an array [closed]

I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time? I am facing a problem where I have about 8 million elements in a file that ...
2
votes
0answers
120 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
vote
0answers
88 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 ...
2
votes
1answer
241 views

Extensions of Matrix-Tree Theorem

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) ...
1
vote
0answers
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 ...
3
votes
1answer
485 views

minimum distance r-dominating set on tree

Given a graph G = (V,E) with edge and vertex weights. The minimum distance r-dominating set problem for a graph G = (V,E) requires to find a set S $\in$ V of smallest vertex-weight such that every ...
26
votes
1answer
607 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
3
votes
1answer
1k views

Steiner tree problem for unweighted graphs

Steiner tree problem for weighted graphs is NP-hard. How about unweighted graphs? That is, given a graph $G=(V,E)$ and a subset $C$ of $V$, find a subtree of $G$ with the least number ...
-1
votes
1answer
149 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 ...