h0ngjun7   9년 전

일반적인 non-weighted undirected graph에서 지름을 O(VE)보다 빨리 찾는 방법이 존재하나요? cactus graph와 같은 특수한 경우에는 linear하게 되고, approximation으로는 tree에서 구할 때처럼 임의의 정점에서 가장 먼 정점(A)을 찾고 A에서 가장 먼 정점을 찾는 걸 반복하는 방법이 있던데 궁금하네요.

댓글을 작성하려면 로그인해야 합니다.