제목 : An Efficient Heuristic Procedure for Partitioning Grapths
Abstract :
cost를 가진 edge의 edge cut을 cost합이 최소화 하는 방향으로 주어진 크기의 부분집합으로 그래프의 노드 분할에 대한 문제를 고려했다.
예로 전자 회로의 보드에 최소연결로 부품을 올리기 위한 문제가 있음.
휴리스틱한 방법으로 최적의 분할을 찾기 위해 이 논문을 작성함.
Intro :
주어진 그래프 G는 cost를 가진 Edge로 이루어져있고, Edge의 cost 합이 최소화되게 잘라서 주어진 최대 크기보다 크지않은 G의 부분집합으로 나누는 문제를 다룸.
전자회로의 부품을 카드사이의 연결을 최소화하고 인쇄된 카드에 위치시키는 문제에서 부품이 그래프의 노드이고, 회로 연결이 edge이다. 어떤 카드에든 최대의 부품을 올리는 것이 목적이다.
카드 사이의 연결은 카드위에서의 연결보다 더 높은 cost이다.
페이징된 메모리 구조의 컴퓨터에서 페이징된 프로그램을 사용할때 자연적으로 발생한다.
결론 :
그래프 분할에 대한 휴리스틱한 해법을 2way, multi way로 설명하고있고, 그에 대한 정의와 수식들을 보여주고있다.
댓글