On VHV-Routing in Channels with Irregular Boundaries

Abstract

This paper discusses the VHV-channel-routing problem in irregular channels. We describe a branch-and-bound algorithm for finding optimal solutions for this problem. The algorithm partitions the channels into boxes, and searches for the optimal among the various mappings of the horizontal net segments to the boxes. We discuss three different branching strategies for the algorithm. Heuristic algorithms based on the branching strategies are also discussed. We also show that VHV routing is NP-hard for irregular channels. © 1989 IEEE