一种连通孔最小化的通道布线算法

摘要

本文根据线网连接端的位置引进了线网位置关系图和线网分层图,从而把连通孔最小化通道布线问题归结为:拆开最少数目的线网使得线网分层图转换成可二着色图。文中导出了通道布线最少连通孔数的公式,并在此基础上提出了一种连通孔最小化通道布线算法。