3
$\begingroup$

Consider the next problem. Given a large oriented graph find its diameter: maximal length over all shortest directed paths between every pair of vertices. Graph is strongly connected. It is allowed to give lower and upper bounds on the answer. Time complexity should be linear or close to it.

Suppose I solved the problem and I want to prove it. Moreover I want the proof can be checked in linear time: graph is large.

Lower bound is easy. Just let me give two vertices on neccessary distance. Upper bound is harder. I can give a vertex and ask to estimate the furthest vertex reachable by forward, and then by backward, edges. Then I sum up these distances and call it upper bound.

The problem that my upper bound doesn't look tight. Can anybody suggest something better?

$\endgroup$
  • $\begingroup$ This looks tight for directed paths? $\endgroup$ – András Salamon Nov 1 '13 at 23:01
  • $\begingroup$ Yes, if the graph is just a chain of vertices connected by edges, upper bound works very well. $\endgroup$ – Vsevolod Oparin Nov 2 '13 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.