Questions about a special kind of graphs, namely connected and cycle-free ones.
4
votes
1answer
69 views
Reachability queries on a tree in $O(1)$ time with $O(n+m)$ time preprocessing
I am given an undirected tree $T$ in the usual graph theoretic sense. Given a vertex $v$ and an edge $(v,u)$ incident to $v$, I need to answer queries of the form return any leaf of $T$ that is ...
1
vote
0answers
26 views
Assigning a formula to an approximate value
Let's say I have a software that calculates integrals, formally if possible and if not, then it computes an approximation by taking a small $dt$. Of course if the integral is an unknown number, I ...
0
votes
0answers
40 views
Lowest Common Ancestor Problem
I have been trying to solve this LCA problem for many queries on a tree of size ~ 10^5
There are about 10^5 queries that have to be handled. What is the best way to do this? I am aware of the naive ...
1
vote
1answer
22 views
Find the number of topological sorts in a tree
Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.
I've tried thinking what would be the best for m to define it but couldn't get ...
0
votes
0answers
29 views
Nash Equilibrium in Tree of Bounded Degree
I have an exercise which I can't solve.
Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
2
votes
1answer
172 views
Trouble understanding this dynamic programming solution
Here is the question:
I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.
for ...
-3
votes
1answer
71 views
Proving that the largest number of leaves in an $n$-ary tree of height $k$ is $k^n$
How to prove that the largest number of leaves in an $n$-tree of height $k$ is $k^n$?
2
votes
2answers
93 views
Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree
There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.
For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
For each ...
1
vote
1answer
67 views
What makes Bayesian Networks decomposable into joint trees?
Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.
...
2
votes
1answer
67 views
Euclidean Steiner Tree Question in Approximation Algorithms
Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$.
...
2
votes
1answer
79 views
How to generate uniformly random binary trees?
Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?
2
votes
1answer
39 views
Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$
Given we change the rule to:
$-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$
I was wandering whether it's possible and how would it affect the trees' height, would it ...
7
votes
1answer
277 views
Longest path in an undirected tree with only one traversal
There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:
Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
5
votes
2answers
80 views
Given a tree, find a vertex which maximizes the minimum distance to any leaf
If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.
I am sure this problem has been studied before.
Does anybody know the ...
2
votes
0answers
48 views
Which data structure to use to solve equations?
Let's say I have two equations for a geometric object (a rectangle):
$\left\{
\begin{array}{l}
x \ge 0 \\
y \ge 0 \\
A \ge 0 \\
P \ge 0 \\
A = x*y \\
P = 2*x + 2*y
...
4
votes
1answer
46 views
Prize collecting steiner tree
I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of ...
7
votes
1answer
130 views
Linear time labeling algorithm for a tree?
I have an undirected tree whose vertices I want to label. The leaf nodes should be labeled one. Then, assume the leaves were removed. In the tree that remains, the leaves should be labeled two. This ...
2
votes
1answer
82 views
How to analyze the Steiner tree problem?
I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps.
1) Look up what the Steiner tree problem is.
2) Find a ...
10
votes
1answer
468 views
BIT: What is the intuition behind a binary indexed tree and how was it thought about?
A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in ...
2
votes
1answer
123 views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
0
votes
2answers
193 views
Longest path in undirected tree [duplicate]
Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge ...
3
votes
3answers
113 views
Find node that splits tree in half
Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is ...
3
votes
1answer
122 views
Algorithm for determining minimal set of covering prefixes
I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set.
For instance, if my set is:
...
0
votes
1answer
105 views
Notation Conventions for Tree Data Structures
I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to ...
1
vote
1answer
105 views
Calculating traversal position of a node in a full binary tree, given its path
Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in ...
2
votes
1answer
52 views
Is this data structure a hypertree or only isomorphic trees?
I have a data structure described as following:
- It's a collection of trees.
- Each tree has the same structure.
- Each tree has information of diferent nature.
...
2
votes
1answer
173 views
Why does a suffix tree have a linear number of nodes (relative to input string size)?
Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.
1
vote
1answer
250 views
B-Tree Is degree and order both are the same thing related to a B-Tree
I know the term order of a B-tree. Recently I heard a new term B tree with minimum degree of 2.
We know the degree is related with a node but what is degree of a tree.
Is degree imposes any kind of a ...
3
votes
2answers
699 views
Why is the minimum height of a binary tree $\log_2(n+1) - 1$?
In my Java class, we are learning about complexity of different types of collections.
Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
3
votes
1answer
79 views
Constructing a tree from disjoint graphs
I will preface my question with the definition of a simple tree that applies to my question:
A simple tree is an undirected and connected graph with no cycles.
I am having difficulty coming up ...
2
votes
1answer
90 views
Size of the universe for van Emde Boas Trees
In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde ...
3
votes
1answer
356 views
Explanation of recursive structure of Van Emde Boas Tree
From Van Emde Boas trees lecture:
We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of
a bit vector, but shrink the universe size recursively by a square
root at each ...
8
votes
3answers
177 views
Finding the height of all nodes in a forest
I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges ...
6
votes
2answers
159 views
Separate all leaves of a weighted tree with minimum weight cuts
This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete ...
8
votes
0answers
155 views
On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
3
votes
1answer
246 views
What is postorder traversal on this simple tree?
Given the following tree:
Which traversal method would give as result the following output: CDBEA?
The answer in my study guide is Postorder, but I think postorder would output: DEBCA. Am I ...
4
votes
2answers
225 views
Counting trees (order matters)
As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In ...
7
votes
1answer
173 views
What use are the minimum values on minimax trees?
Consider a minimax tree for an adversarial search problem. For example, in this picture (alpha-beta pruning):
When marking the the tree with $[\min,\max]$ values bottom-up, we first traverse node ...
12
votes
5answers
273 views
Efficient compression of unlabeled trees
Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store ...
6
votes
3answers
882 views
Algorithm to test whether a binary tree is a search tree and count complete branches
I need to create a recursive algorithm to see if a binary tree is a binary search tree as well as count how many complete branches are there (a parent node with both left and right children nodes) ...
