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 a acyclic connected graph.

learn more… | top users | synonyms

0
votes
0answers
37 views

Generalised Weighted Vertex Cover on Trees

Given a rooted vertex-weighted tree, find a minimum weighted vertex subset S such that every connected component on G-S has atmost k vertices. Is this problem already solved in polynomial time? ...
0
votes
0answers
51 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
0answers
32 views

Eioknal Equation solver with different grid densities

The Fast Marching Method, Fast Iterative Method, and Fast Sweeping Method are three ways of solving the Eikonal Equation on a discrete grid, essentially just a wavefront spreading out from initial ...
0
votes
2answers
62 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
111 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
77 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
161 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
54 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
121 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 ...
15
votes
0answers
156 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 ...
2
votes
1answer
258 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
113 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 ...
-2
votes
1answer
80 views

Has anyone ever mixed strings in a language with position?

Let the alphabet $\Sigma$ be extended to include $\bullet$, the concatenation point character. Define concatenation of such strings to be: (by example): $$ s\cdot t = (\omega \bullet \gamma ) \cdot ...
2
votes
0answers
131 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 ...
1
vote
1answer
199 views

Spell Checker with BK tree and edit distance that accounts for transpositions

I want to try and write code for a BK tree using a certain edit distance that accounts for transpositions for a spell corrector. I've looked into Damerau-Levenshtein distance, but the triangle ...
1
vote
0answers
151 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
0answers
82 views

Linear time algorithm for computing the labels of leaves in a recursively defined tree [closed]

The original copy of the question on MSE. Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows: The root has label $S$, for each ...
4
votes
3answers
253 views

Chomsky hierarchy for tree structures

I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$. Is there a similar hierarchy for ...
6
votes
2answers
280 views

Caterpillar decomposition of trees

Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the ...
4
votes
1answer
267 views

Multidimensional B+ tree

I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach. The idea is a 'stacked' B+ tree implementation ...
10
votes
2answers
486 views

What is a zipper, and how does it relate to a tree-like structure?

I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers ...
0
votes
1answer
126 views

Cubic (3-regular) graph spanning tree

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes): Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ...
2
votes
1answer
194 views

Does the order of insertion affect the topology of an R-Tree

Say I have 2 permutations of the the same set of elements. I create 2 R-Trees, one for each permutation. Do I end up with 2 structurally identical R-Trees or not? PS: My elements are rectangles on a ...
5
votes
0answers
136 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 ...
11
votes
0answers
395 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)$ ...
2
votes
0answers
67 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 ...
0
votes
1answer
250 views

Is there a characteristic function of a tree?

Consider a set of trees $T=\{T_{\alpha}\}$, and for any $T_{\alpha}\in T$, $T_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' ...
4
votes
1answer
483 views

Trees that structure partially ordered data

Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node ...
14
votes
3answers
2k views

Merging Two Binary Search Trees

I'm looking for an algorithm to merge two binary search trees of arbitrary size and range. The obvious way I would go about implementing this would be to find entire subtrees whose range can fit into ...
9
votes
2answers
3k views

efficient diff algorithm for trees and Levenshtein distance

I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem. Also, suppose that between ...
1
vote
1answer
279 views

Remove specific edge from ST (link-cut) tree

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time: CUT(v) Deletes the edge from v to its parent JOIN(v, ...
-4
votes
1answer
3k views

unique binary tree from preorder and postorder traversals of a full binary tree [closed]

If we have a preorder and postorder traversals of a full binary tree T(i.e every internal node have exactly 2 children). can we uniquely construct the corresponding full binary tree T. If so.. could ...
12
votes
4answers
632 views

P-complete problems on trees

This question is related to one of my previous questions, NP-hard problems on trees. I am looking for problems that are P-complete on trees.
19
votes
4answers
9k views

Why would one ever use an Octree over a KD-tree?

I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar ...
8
votes
1answer
313 views

Minimum degree of the “tree graph”

Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a ...
-3
votes
3answers
137 views

Working with all leaves on a certain level of a b-tree

I want to work with a b-tree of any size. I want to do something with all leaves of the lowest depth $d$. Then if a certain condition holds, I want to recursively consider the same condition for the ...
0
votes
0answers
186 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?
5
votes
0answers
285 views

Efficient algorithms for searching a collection of trees

I have a large dataset of trees and I would like to search it by specifying a treelet (connected subgraph). The query should return all the occourrences of the treelet in the dataset. Are there ...
3
votes
1answer
605 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? ...
4
votes
3answers
245 views

Storage system for large quantities of unique key value pairs optimized for insert

Background I'm in the process of attempting to improve part of our data storage and analysis architecture. Without getting into a lot of details, at a certain part of our data analysis process we ...
9
votes
6answers
683 views

A data structure for sets of trees.

Tries allow for efficient storage of lists of elements. The prefixes are shared so it is space efficient. I am looking for a similar way to efficiently store trees. I would like to be able to check ...
4
votes
1answer
329 views

Dynamic Tree Marked Ancestor Queries

Assuming a rooted tree $T$ with vertices $V$, I am maintaining subsets of $V$, for example $M \subseteq V$ whose vertices are associated with particular labels or values. $V$ is dynamic in that it ...
11
votes
0answers
220 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 ...
15
votes
3answers
444 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
11
votes
1answer
246 views

Minimum weight subforest of given cardinality

This question was motivated by a question asked on stackoverflow. Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$). ...
16
votes
2answers
1k views

Finding the distance between two polynomials (represented as trees)

A colleague who works on genetic programming asked me the following question. I first tried to solve it based on a greedy approach, but on a second thought, I found a counterexample to the greedy ...
5
votes
1answer
279 views

Searching nodes in semi-splay tree

If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations. My course also says that if you search for a node and the ...
6
votes
1answer
267 views

Optimal Self Balancing Trees with Canonical Form?

Are any efficient [O(log n)] self balancing trees that are canonical? By canonical I mean that for any set of data inserted into the tree, inserting it after any permutation results in the same tree. ...
5
votes
0answers
295 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 ...
9
votes
2answers
731 views

How do I choose a functional dictionary data structure?

I've read a bit about the following data structures: Bagwell's Ideal Hash Tries Larson's Dynamic hash tables Red-Black trees Patricia trees ...and I'm sure there are a lot of others out there. ...