Channel routing in knock-knee mode: Simplified algorithms and proofs (Q1091149): Difference between revisions

We give unified and simplified algorithms and proofs for three results on channel routing in knock-knee mode. Let P be a channel routing problem with density \(d_{\max}.\) a) [Rivest/Baratz/Miller, Preparata/Lipski]. If all nets in P are two- terminal nets then \(d_{\max}\) tracks suffice. b) [Preparata/Sarrafzadeh]. If all nets in P are two- or three-terminal nets then \(\lfloor 3d_{\max}/2\rfloor\) tracks suffice. c) [Sarrafzadeh/Preparata]. \(2d_{\max}-1\) tracks always suffice. In all three cases a solution can be found in linear time; this is an improvement in case b).