# 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.

114 questions
Filter by
Sorted by
Tagged with
48 views

### Why LOUDS is considered succinct coding?

LOUDS encoding is widely cited as succinct, e.g., in the papers, in Github repos, etc. It is straightforward that LOUDS takes 2n bits for encoding an ordered tree ...
• 113
1 vote
86 views

### Is it possible to encode the structure of a binary cardinal tree with n nodes using only n bits?

By binary cardinal tree, I mean a tree with degree 2. The question confuses me because I know LOUDS/DFUDS can encode binary trees with 2n bits; however, this paper claims that it is possible to encode ...
• 113
72 views

### What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
• 228
66 views

### Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
• 228
118 views

### Given $a_i$ -$r$ paths $P_i$ in a planar graph construct a tree spanning $a_i$ such that each root to leaf path intersects few $P_i$

Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and edge disjoint $a_i$-$r$ paths $P_i$ for each $i$ in a planar graph $G$. I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ ...
• 228
107 views

### Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
• 181
41 views

### Homeomorphic subtree extraction in integer sorting time

Background Given a rooted, binary tree $T$ with leaves bijectively labeled by $\{1, \ldots, n\}$ (a "phylogenetic tree"). Let $L \subseteq \{1, \ldots, n\}$, and $|L| = k$. The homeomorphic ...
106 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, ...
• 9,677
167 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)$ ...
• 37.5k
68 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)$. ...
• 177
383 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
157 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
247 views

• 133
1 vote
69 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
168 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
54 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$'...
526 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 vote
92 views

157 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
564 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
114 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 ...
150 views

• 9,677
1 vote
289 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
464 views

• 9,478
285 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,776
332 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,478
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.6k
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