Post Reopened by Yuval Filmus algorithms

occurred Apr 20, 2017 at 7:44

Typo ^^'

Source Link

edited Apr 20, 2017 at 7:16

Stellaris

23
1
6

Given an acyclic undirected graph alike to this one :

(Here the centers arecenter is the nodesnode '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost notingnothing about this online

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost noting about this online

Given an acyclic undirected graph alike to this one :

(Here the center is the node '2', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost nothing about this online

added 41 characters in body

Source Link

edited Apr 20, 2017 at 6:37

Stellaris

23
1
6

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost noting about this online

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost noting about this online

Corrected the question because of duplicates

Source Link

edited Apr 20, 2017 at 6:29

Stellaris

23
1
6

Efficient Algorithm to computercompute radius of tree

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter

Efficient Algorithm to computer radius of tree

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

Efficient Algorithm to compute radius of tree

Given an acyclic undirected graph alike to this one :

(Here the centers are the nodes '2' and '6', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter

2

duplicates list edited from Longest path in an undirected tree with only one traversal to Longest path in an undirected tree with only one traversal, Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

Link