2d (Two Dimensional) - 1 Lower Bound 2-Layer Knock-Knee Channel Routing.

摘要

In this paper, we describe a 2-point net channel routing problem with density d that requires channel width 2d - 1 in the 2-layer knock-knee channel routing model. This means that the (2d - 1)-track algorithms of Rivest, Baratz and Miller, Bolognesi and Brown, Frank, Mehlhorn, Preparata and Sarrafzadeh and Berger, Brady, Brown and Leigton are, in some cases, optimal. Thus any improvement of these algorithms must rely on problem features other than density (such as flux), or must make fundamental changes in the wiring model (such as increasing the number of layers or allowing wires to overlap.) Keywords: Integrated circuits, Automated layout systems, Heuristic methods. (kr)