Diameter problem

Правка en1, от kpw29, 2016-09-12 21:36:25

Have you ever seen a problem connected to graphs diameter, where it is used in complexity?

For example: http://main.edu.pl/en/archive/oi/21/tur .

Model solution goes O( (1 + sqrt(2)) ^ T) * (n + m) ), where n is number of vertices, m — edges and T is the longest path which we can encounter in it. However, longest path is not a diameter. I've just wanted to show what I am talking about.

Any help with finding such a problem would be highly appreciated. Thanks in advance!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский kpw29 2016-09-12 21:36:25 505 Initial revision (published)