On river routing with minimum number of jogs

The one-layer wiring problem of providing a one-to-one connection between two sets of terminals that lie on two horizontal lines by means of wires, which are in the forms of disjoint rectilinear curves on a unit-grid (where one unit is the minimum spacing between two wires), is called the river routing problem. The minimization of horizontal wire segments for a one-layer rectilinear river routing model is discussed. For given separation s, the list of simple jog sequences is merged into a list of compound jog sequences that leads to the concept of feasible cuts. An algorithm that finds a feasible cut whose corresponding layout has the minimum possible total number of horizontal wires segments is given. An algorithm that gives a complete description of the layout is also given. Both algorithms run in time O ( n * s )