Abstract | ||
---|---|---|
Signal flow directions of MOS transistors have been used in many CAD tools. A graph theoretic approach is presented for determining these directions. A MOS circuit is represented using several undirected graphs called ST-graphs. The direction assignment problem is modeled as a two paths problem in each ST-graph. Necessary and sufficient conditions under which all edges in an ST-graph are unidirectional are derived. A linear time algorithm is presented that assigns directions to all edges in an ST-graph if they all unidirectional. If bidirectional edges exist, the algorithm assigns directions to most edges in the ST-graph, and the remaining edges are resolved by a sequence of additional algorithms. Experimental results validate the performance benefits of this approach.<> |
Year | DOI | Venue |
---|---|---|
1990 | 10.1109/ICCAD.1990.129962 | Santa Clara, CA, USA |
Keywords | Field | DocType |
circuit CAD,graph theory,insulated gate field effect transistors,CAD tools,MOS transistors,ST-graphs,graph theoretic approach,linear time algorithm,signal flow directions,undirected graphs | Cad tools,Graph theory,Graph,Computer science,Algorithm,Electronic engineering,Assignment problem,Time complexity,Transistor,Signal-flow graph | Conference |
Citations | PageRank | References |
6 | 0.63 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kuen-jong Lee | 1 | 6 | 0.63 |
rajiv gupta | 2 | 4301 | 364.53 |
Melvin A. Breuer | 3 | 1372 | 268.69 |