6th Great Lakes Symposium on VLSI
On Locally Optimal Breaking of Complex Cyclic Vertical Constraints in VLSI Channel Routing
Ames, IA
March 22-March 23
ISBN: 0-8186-7502-0
Existing theory has supported deterministic polynomial time procedures for locally optimal breaking (LOB) of two classes of directed circuits (DC) in the vertical constraint graph, the classes of vertex disjoint DC?s, and of couples of connected DCs. New LOB theory is reported that supports procedures for LOB of any number of DC?s sharing a common vertex, or a common path, and of DC?s in uniform ladder VCG?s. A significant aspect of the new theory is that it relies on procedures for couples of connected DCs as tools for breaking more complex structures of connected DC?s. Application of the theory in genetic channel routers is reported elsewhere.