티스토리 뷰

공부

Dominator Tree

구사과 2018.01.13 00:13

방향 그래프의 Dominator Tree의 유래, 개념에 대해서 짤막한 글을 써보았습니다.

Dominator Tree를 빠르게 구하는 알고리즘에 대한 언급은 없습니다. Dominator Tree를 빠르게 구하는 알고리즘은, 그 증명 방법과 내용이 상당히 길고 복잡하기 때문입니다. 개인적인 생각으로는 그 부분까지 이해할 필요는 없고, 구현체만 팀노트에 넣어도 문제 해결에 충분하다고 생각합니다.

dominator_tree.pdf



'공부' 카테고리의 다른 글

RUN@KAIST 2018 겨울 1주차 연습 문제  (1) 2018.01.16
ICPC 2015 Tsukuba K. Min-Max Distance Game  (0) 2018.01.14
Dominator Tree  (1) 2018.01.13
2017 ICPC 팀노트 공개  (3) 2017.11.22
(팀연습) JAG Summer Camp 2014  (0) 2017.11.21
ACM-ICPC Daejeon Regional 2017  (12) 2017.11.13
댓글
댓글쓰기 폼
공지사항
Total
134,019
Today
61
Yesterday
154