본 게시글은 Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication, Oren weimann, Raphael yuster 을 읽고 작성한 글입니다.
1. Title
Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
2. Abstract
n개의 정점을 가진 G=(V, E)의 거리 민감도 오라클은, 간선 고장시 최단 경로를 보고할 수 있는 데이터구조.
오라클에 대한 쿼리는 그래프 G'=(V, E\S)에서, u에서 v로 가는 최단 경로를 반환한다.
이 논문에서 제시하는 알고리즘은, 거리 민감도 오라클을 구축하는 랜덤화된 (몬테카를로) 알고리즘이다.
3. 목표
그래프에서 간선이나 정점에 문제가 있을 때 최단 경로를 빠르게 찾기 위해 Fast Matrix Multiplication을 통한 거리 민감도 오라클 및 대체 경로에 대한 알고리즘 구현
즉, 여러 간선이나 정점 고장을 처리하기 위한 효율적인 거리 민감도 오라클 개발,
대체 경로 문제를 위한 빠른 알고리즘 개발이 목적.
4. 방법
(1) 랜덤 서브그래프 생성
원본 그래프 G의 각 간선을 독립적 확률로 제거 (제거 비율은 그래프 크기, 허용 가능한 고장 개수, 알고리즘 정확도, 성능 간 균형에 대한 파라미터로 결정)
위 과정을 r번 반복해 r개의 랜덤 서브그래프를 생성
이렇게 하면 모든 가능한 고장 상황에 대해 미리 계산하는 것이 아니라,
랜덤 서브그래프를 통해 일부 상황만을 미리 계산해두고, 쿼리 시에는 해당 서브그래프들을 활용해 효율적으로 답을 찾을 수 있다.
(2) 중요 정점 집합 B 선택
집합 B의 크기를 설정하고, 그 크기의 정점을 선택해서 B를 구성한다.
따라서 각 정점이 B에 포함될 확률은 동일하다.
이렇게 하면 B에 속한 정점들이 긴 경로를 짧게 분할하는 역할을 할 수 있다. 또, B의 크기를 적절히 조절하면서 쿼리 시간을 줄이면서도 정확한 결과를 얻을 수 있다.
(3) 빠른 행렬 곱셈을 이용한 거리 계산
Yuster-Zwick 알고리즘 (모든 최단 경로(APSP)를 효율적으로 계산하기 위한 알고리즘)
(4) 가격 함수를 이용한 그래프 재가중치화
가격 함수란, 그래프 G=(V, E)의 각 정점 v에 대해 실수 값을 할당하는 함수 pie(v)를 말한다.
각 간선 (u, v)의 길이를 원래 길이 w(u, v)에 가격 함수를 빼고 더해서 변환함으로써 정의한다.
즉, 변환된 길이는 w_pie(u, v) = w(u, v) + pie(u) - pie(v) 이다.
이때 모든 간선에 대해 변환된 길이가 0 이상이라면, 가격 함수는 feasible하다고 한다.
5. 결과
민감도 오라클 구축
대체 경로 문제에 대해 시간 알고리즘 제시
6. 향후계획
(근사 거리를 허용하는 경우) 쿼리 시간 개선
무제한 가중치를 가진 유향 그래프에서 대체 경로 문제를 준3차 시간에 해결하는 방법
'논문 살피기' 카테고리의 다른 글
본 게시글은 Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication, Oren weimann, Raphael yuster 을 읽고 작성한 글입니다.
1. Title
Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
2. Abstract
n개의 정점을 가진 G=(V, E)의 거리 민감도 오라클은, 간선 고장시 최단 경로를 보고할 수 있는 데이터구조.
오라클에 대한 쿼리는 그래프 G'=(V, E\S)에서, u에서 v로 가는 최단 경로를 반환한다.
이 논문에서 제시하는 알고리즘은, 거리 민감도 오라클을 구축하는 랜덤화된 (몬테카를로) 알고리즘이다.
3. 목표
그래프에서 간선이나 정점에 문제가 있을 때 최단 경로를 빠르게 찾기 위해 Fast Matrix Multiplication을 통한 거리 민감도 오라클 및 대체 경로에 대한 알고리즘 구현
즉, 여러 간선이나 정점 고장을 처리하기 위한 효율적인 거리 민감도 오라클 개발,
대체 경로 문제를 위한 빠른 알고리즘 개발이 목적.
4. 방법
(1) 랜덤 서브그래프 생성
원본 그래프 G의 각 간선을 독립적 확률로 제거 (제거 비율은 그래프 크기, 허용 가능한 고장 개수, 알고리즘 정확도, 성능 간 균형에 대한 파라미터로 결정)
위 과정을 r번 반복해 r개의 랜덤 서브그래프를 생성
이렇게 하면 모든 가능한 고장 상황에 대해 미리 계산하는 것이 아니라,
랜덤 서브그래프를 통해 일부 상황만을 미리 계산해두고, 쿼리 시에는 해당 서브그래프들을 활용해 효율적으로 답을 찾을 수 있다.
(2) 중요 정점 집합 B 선택
집합 B의 크기를 설정하고, 그 크기의 정점을 선택해서 B를 구성한다.
따라서 각 정점이 B에 포함될 확률은 동일하다.
이렇게 하면 B에 속한 정점들이 긴 경로를 짧게 분할하는 역할을 할 수 있다. 또, B의 크기를 적절히 조절하면서 쿼리 시간을 줄이면서도 정확한 결과를 얻을 수 있다.
(3) 빠른 행렬 곱셈을 이용한 거리 계산
Yuster-Zwick 알고리즘 (모든 최단 경로(APSP)를 효율적으로 계산하기 위한 알고리즘)
(4) 가격 함수를 이용한 그래프 재가중치화
가격 함수란, 그래프 G=(V, E)의 각 정점 v에 대해 실수 값을 할당하는 함수 pie(v)를 말한다.
각 간선 (u, v)의 길이를 원래 길이 w(u, v)에 가격 함수를 빼고 더해서 변환함으로써 정의한다.
즉, 변환된 길이는 w_pie(u, v) = w(u, v) + pie(u) - pie(v) 이다.
이때 모든 간선에 대해 변환된 길이가 0 이상이라면, 가격 함수는 feasible하다고 한다.
5. 결과
민감도 오라클 구축
대체 경로 문제에 대해 시간 알고리즘 제시
6. 향후계획
(근사 거리를 허용하는 경우) 쿼리 시간 개선
무제한 가중치를 가진 유향 그래프에서 대체 경로 문제를 준3차 시간에 해결하는 방법
