597 views

### Print Binary Tree Diameter Path [duplicate]

Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT. Print the Longest leaf to leaf path in a binary tree and its ...
122 views

### LInear time algorithm to find the diameter of a tree [duplicate]

This is NOT HW, this is from Skienas book, and I just couldn't solve it at all. Please give me a hand here, in understanding and solving it, thanks. Let G = (V, E) be a binary tree. The distance ...
27k views

### The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| \cdot |E|)$ ${O}(|V|^2\cdot |E|)$ ${O}(|V|\cdot |E|^2)$ The diameter of a ...
40k views

### Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
16k views

### Find the longest path from root to leaf in a tree

I have a tree (in the graph theory sense), such as the following example: This is a directed tree with one starting node (the root) and many ending nodes (the leaves). Each of the edge has a length ...
2k views

### Longest path in a cyclic, directed and weighted graph

I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights. In my research so far I have found out that you need to generate ...
1k views

### Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes ...
395 views

### Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
How can one generate all unlabeled trees with $\le n$ nodes? That is, generate and store the adjacency matrices of those graphs? (not just count them) Visualization of all unlabeled trees with $\le6$...