08/01/1995 09:00 AM
Computer Engineering
Many package routing problems involve routing one set of pins to another set of pins in a single layer without regard to how the pins in each set are connected. We call this type of problem a Planar Pin Assignment and Routing Problem (PPARP). Unlike general routing problems which correspond to the NP-complete multi- commodity flow problem, the pin distribution problem seems to have a natural formulation as a single- commodity flow problem, which suggests that it can be solved efficiently. In this paper, we show that the problem is surprisingly NP-complete.
