평면그래프 문제를 위한 아닐링 알고리즘 = Annealing Algorithms for Graph Planarization Problem

국문 초록 (Abstract)

본 논문에서는 PCB디자인과 VLSI 설계과정 중에 배선처리 문제에 응용될 수 있는 평면그래프 문제를 해결하기 위한 알고리즘을 제안한다. 이 알고리즘에서는 신경회로망의 최적화 기법들 중 MFA(Mean Field Annealing)과 SA(Simulated Annealing)을 근사최적의 해를 구하기 위해 사용한다.
이 알고리즘에서는 일반적으로 평면그래프 문제가 두단계로 처리되어 왔던 것을 하나의 단계로 처리하고, m_e개의 간선(edge)을 갖는 그래프 문제에서 교차가 일어날 수 있는 간선만을 전처리 과정에서 추출하여 이 간선말을 계산 노드로 하는 신경망을 구성한다. 또한 Takefuji의 에너지 함수에서 인수를 고려하지 않도록 단순화하여 학습에 사용하였다. 실험 과정을 통해 기존의 알고리즘의 결과보다 다소 우수한 결과를 산출하며 Takefuji 모델보다 신경망 노드를 적게 사용해 학습할 수 있음을 보였다.

다국어 초록 (Multilingual Abstract)

In this paper, we propose an algorithm for the graph planarization problem which can be applied to a PCB design and a routing problem in the VLSI design processes. MFA and SA, which are neural network optimization tools, are used to find a near-optimal solution.
This algorithm solves the planar graph problem in only one step, which usually took two steps in general. We construct a neural network that consists of computational nodes of selected edges by a preprocessing process. Due to the characteristics of MFA and SA, the energy function is simplified by removing some constraint terms. Simulation results show that this algorithm based on neural network model not only has more higher performance but also uses less nodes for learning than Takefuji's model.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 배경
• 3. 알고리즘 구성
• 4. 실험
• 5. 결론
• 참고문헌
• 저자소개