일반적인 non-weighted undirected graph에서 지름을 O(VE)보다 빨리 찾는 방법이 존재하나요? cactus graph와 같은 특수한 경우에는 linear하게 되고, approximation으로는 tree에서 구할 때처럼 임의의 정점에서 가장 먼 정점(A)을 찾고 A에서 가장 먼 정점을 찾는 걸 반복하는 방법이 있던데 궁금하네요.
찾아봣는데 이런건 있네요
http://stackoverflow.com/questions/18733039/how-do...
http://codeforces.com/blog/entry/4116
댓글을 작성하려면 로그인해야 합니다.
h0ngjun7 9년 전 1
일반적인 non-weighted undirected graph에서 지름을 O(VE)보다 빨리 찾는 방법이 존재하나요? cactus graph와 같은 특수한 경우에는 linear하게 되고, approximation으로는 tree에서 구할 때처럼 임의의 정점에서 가장 먼 정점(A)을 찾고 A에서 가장 먼 정점을 찾는 걸 반복하는 방법이 있던데 궁금하네요.