Permutation diagrams have been used in circuit design to model a set of single point nets crossing a channel, where the minimum number of layers needed to realize the diagram equals the clique number omega(G) of its permutation graph, the value of which can be calculated in O(n log n) time. We consider a generalization of this model motivated by "standard cell" technology in which the numbers on each side of the channel are partitioned into consecutive subsequences, or cells, each of which can be left unchanged or flipped(i.e., reversed). We ask, for what choice of flippings will the resulting clique number be minimum or maximum. We show that whenn one side of the channel is fixed, an ptimal flipping for hte other side can be found in O(n log n) time for the maximum clique number. We provethat the general problem is NP-complete for the minimum clique number and O(n sup 2) for the maximum clique number. Moreover, since the complement of a permuattion graph is also a permutation graph, the same compelxity results hold for the independence number.
展开▼
