Diameter of a Psuedotree

Правка en1, от vamaddur, 2017-07-15 19:57:00

I know how to find the diameter of a tree in linear time, prove the validity of the algorithm used to do so (successive BFS's), and prove why it doesn't work for non-tree connected graphs.

However, I need an algorithm/approach that has better complexity than O(N^2) to find the diameter of a relatively large pseudotree (a tree with one extra edge).

Please help, and thanks in advance!

Теги diameter, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский vamaddur 2017-07-15 22:51:28 9 Tiny change: 'ely large pseudotre' -> 'ely large WEIGHTED pseudotre'
en1 Английский vamaddur 2017-07-15 19:57:00 415 Initial revision (published)