The paper is concerned with solutions to permutation layout problems such that i) no wire passes the upper area of the upper horizontal line, and ii) no wire intersects the lower horizontal line more than once. A necessary and sufficient condition for a problem to have such a solution is given. The set of all the solutions to the given problem is characterized in a graph theoretical way. A linear time algorithm is also given.

In this paper is given a necessary and sufficient condition for a permutation layout problem to have a wiring pattern such that no wire passes the upper area of the upper horizontal line, no wire intersects the lower horizontal line more than once, and between-pins congestion is not more than k, where the portion of the lower horizontal line which is placed to the left (resp., right) of the leftmost (resp., rightmost) terminal is considered to be a between-pins spacing. A linear time algorithm is given for the case k1, based on a graph theoretical representation of the condition.

A high-speed context-free marker controlled and minima imposition-free watershed transform is proposed for efficient multi-object detection and segmentation from a complex background. The context-free markers are extracted from a complex backgrounded multi-object image using a noise tolerant attention operator. These make high speed marker-controlled watershed possible without over-segmentation and region merging. The proposed method presents a marker-constrained labeling that can speed up the segmentation of the marker-controlled watershed transform by eliminating the necessity of the minima imposition. Simulation results show that the proposed method can efficiently detect and segment multiple objects from a complex background while reducing the over-segmentation and computation time.