Questions about a special kind of graphs, namely connected and cycle-free ones.

learn more… | top users | synonyms

-1
votes
1answer
28 views

Height of H-Tree [closed]

I studied VLSI layout design and in that they discussed the most efficient way to layout is using an H-Tree as the area occupied is smallest compared to for example a binary tree. Can anyone ...
3
votes
1answer
37 views

What is the common terminology to refer to the nth ancestor of a tree root?

Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a ...
0
votes
1answer
85 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
2
votes
1answer
35 views

Merge-by-weight to solve reachability problems in trees and DAGs

Let $T = (V, E)$ be a tree with a designated root $r \in V$. The fact that the tree is rooted allows us to speak of "subtrees of $T$ rooted at some node $x \in V$". Let's say we have a (not ...
5
votes
1answer
156 views

What is the expected number of nodes at depth d of a tree after i random insertions

Suppose one wanted to build a tree at random. Let the first insertion at step $i = 1$ be the root node. From here, nodes are inserted into the tree at random one at a time. How would one go about ...
1
vote
1answer
17 views

Do the two huffman trees have the same corpus?

Consider the following Huffman trees: I was asked if those trees can have the same corpus. My answer was no, based on these calculations: For the right tree: $a_1 \le a_2$ $a_1 + a_2 \le a_5$ ...
-1
votes
2answers
83 views

Edge traversals of trees [closed]

I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of ...
0
votes
0answers
8 views

Representative tree from sets of decision trees

I built a set of samples from an imbalanced dataset with two classes through the undersampling technique. Now, from that set of decision trees I would like to choose one representative tree. Is there ...
1
vote
1answer
17 views

Doubt in the correctness of decision tree models for constructing a lower bound

If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$. But with the decision tree model, the number of leafs is ...
0
votes
1answer
36 views

the height of a tree given n nodes and a condition [closed]

I came across a question on which I got totally stuck :( a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at ...
1
vote
0answers
31 views

Binary search tree with $n$ internal vertices [closed]

How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?
2
votes
0answers
47 views

What are applications of alphabetic trees?

Earlier this week a paper was released describing an algorithm for building optimal alphabetic ternary trees. The alphabetic property as described on Wikipedia as Alphabetic trees are Huffman ...
4
votes
0answers
87 views

Huffman tree and maximum depth

Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?
3
votes
0answers
47 views

How to go from a DAG model to bounded treewidth? [closed]

Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps: moralisation (connect variables that have the same child, drop directions) triangulation ...
-1
votes
1answer
44 views

Satisfying condition to be in minimum spanning tree of an edge (maximum weight)

Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always ...
1
vote
1answer
55 views

What is this algorithm? Create a tree's equivalent hierarchical network

This question was originally posted here: http://stackoverflow.com/q/20735339/2305618 I am surely not the first to have implemented code to perform the following graph transformation. But try as I ...
1
vote
1answer
39 views

Doesn't post-order traversal require subtrees to be evaluated separately?

Consider this tree: If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in ...
-1
votes
1answer
69 views

Finding number of maximum independent sets in tree, using dynamic programming

I'm quite stuck trying to answer this. The problem of finding the size of the maximum independent set in a tree using dynamic programming is well documented and many solutions are around. I've been ...
9
votes
1answer
136 views

Data structure for map on intervals

Let $n$ be an integer, and let $\mathbb{Z}$ denote the set of all integers. Let $[a,b]$ denote the interval of integers $\{a,a+1,a+2,\dots,b\}$. I am looking for a data structure to represent a map ...
6
votes
3answers
658 views

Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar ...
3
votes
2answers
203 views

Priority queue with unique elements and sublinear time merge?

Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time. I am looking for a priority queue that merges in ...
3
votes
2answers
167 views

Algorithm to determine if recursion was breadth first or depth first

Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have ...
0
votes
0answers
111 views

Updating an AVL Tree Based On Balance Factors

I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it? Background: Let the balance factor ...
3
votes
1answer
51 views

Numbering of unlabelled trees

For labelled trees there are the Pruefer numbers that uniquely identify them. Is there a similar numbering system for unlabelled trees?
15
votes
0answers
314 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 ...
4
votes
1answer
85 views

Find equidistant triplets in a tree

Given a tree $T$ with $n$ vertices, we want to find the number of triplets of vertices $(a,b,c)$ such $d(a,b) = d(b,c) = d(c,a)$ where $d$ is the distance function (length of the shortest path between ...
2
votes
1answer
113 views

Number of Independent Sets in a tree

(I've been stuck on this homework assignment for far too long) I need to find the number of independent sets in a tree. For example, say the set of nodes in a tree is {A, B, C, D, E}. B and C are ...
0
votes
2answers
108 views

Why the height of the weight balanced tree is logarithmic

Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?
2
votes
1answer
657 views

Explanation of Heavy light decomposition

Can anyone explain heavy light decomposition of trees or give a resource to read it from? I have already gone through http://ipsc.ksp.sk/2009/real/solutions/l.html which is the best i could find but ...
2
votes
0answers
61 views

Which component sizes do we observe while randomly deconstructing a tree?

Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
3
votes
1answer
307 views

How to query and update ranges of arrays?

I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array. Decrease elements in range $[L,R]$ by $X$. Count the number of negative elements in range ...
2
votes
1answer
172 views

Queries on Tree

We have a tree with $N$ nodes. $N \le 10^5.$ Each node has a value $V$ associated with it. Now we have $Q$ $(\le 10^5)$ queries. There are two types of queries: Q X Y: in this type of query we have ...
5
votes
1answer
128 views

Origins of the Segment tree data structure

I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times ...
3
votes
2answers
156 views

Constructing Tree (forest) from Ancestor function

Question: Suppose I have a set of male people, and a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) ...
1
vote
1answer
199 views

How does insertion work in an AVL tree?

From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, ...
5
votes
1answer
138 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
70 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
75 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
50 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
47 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 ...
1
vote
1answer
242 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 ...
-4
votes
1answer
228 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
1k 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
97 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
105 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
359 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
54 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 ...
12
votes
1answer
3k 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'$. ...
6
votes
2answers
242 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 ...
4
votes
2answers
124 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 ...