A new efficient heuristic algorithm of O($\mid{V}\mid\cdot\mid{e}\mid$) for network partitioning via the concept of connection index of weighted graph is presented, where $\mid{V}\mid$, $\mid{e}\mid$ are the number of vertices and edges, respectively. And the schemes for making the associated graph for node tearing analysis and IC layout are considered.
The experimental results show that our algorithm is very efficient and yields near optimal solutions.
Finally two applications of the network partitioning in CAD are presented. One is general diakoptic analysis and the other is decomposed topological analysis.
회로망 분해는 콤퓨터를 이용한 대형 회로의 설계에 있어서 거의 필수적이며 NP-Complete 문제에 속한다. 이 논문에서는 연결지수를 정의하고 이를 통한 그라프분해 방법을 제안했는데 그의 연산 복잡도는 O($\mid{V}\mid\cdot\mid{e}\mid$) 이다. 여기서 $\mid{V}\mid$ 는 점의 수, $\mid{e}\mid$ 는 기둥의 수를 나타낸다. 그리고 집적 회로의 설계나 회로의 분해를 통한 해석에 적절한 그라프 변환에 대해 고려했다. 실험결과는 매우 빠르고 적절한 분해를 가져옴을 보여준다. 이러한 분해를 통한 회로망의 해석에 대해 고려하고 이러한 개념을 위상적분석에 적용했다.
