References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9
QUADRATIC 0-1 PROGRAMMING 8S 9. 1 Energy Minimization 86 9. 2 Notation
and Tenninology . . . . . . . . . . . . . . . . . 87 9. 3 Minimization
Technique . . . . . . . . . . . . . . . . . . 88 9. 4 An Example . . . .
. . . . . . . . . . . . . . . . . . . . 92 9. 5 Accelerated Energy
Minimization. . . . . . . . . . . . . 94 9. 5. 1 Transitive Oosure . . .
. . . . . . . . . . . . . . 94 9. 5. 2 Additional Pairwise Relationships
96 9. 5. 3 Path Sensitization . . . . . . . . . . . . . . . . . 97 9. 6
Experimental Results 98 9. 7 Summary. . . . . . . . . . . . . . . . . .
. . . . . . . . 100 References . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 100 10 TRANSITIVE CLOSURE AND TESTING 103 10. 1 Background
. . . . . . . . . . . . . . . . . . . . . . . . 104 10. 2 Transitive
Oosure Definition 105 10. 3 Implication Graphs 106 10. 4 A Test
Generation Algorithm 107 10. 5 Identifying Necessary Assignments 112 10.
5. 1 Implicit Implication and Justification 113 10. 5. 2 Transitive
Oosure Does More Than Implication and Justification 115 10. 5. 3
Implicit Sensitization of Dominators 116 10. 5. 4 Redundancy
Identification 117 10. 6 Summary 119 References . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 119 11 POLYNOMIAL-TIME TESTABILITY 123
11. 1 Background 124 11. 1. 1 Fujiwara's Result 125 11. 1. 2
Contribution of the Present Work . . . . . . . . . 126 11. 2 Notation
and Tenninology 127 11. 3 A Polynomial TlDle Algorithm 128 11. 3. 1
Primary Output Fault 129 11. 3. 2 Arbitrary Single Fault 135 11. 3. 3
Multiple Faults. . . . . . . . . . . . . . . . . . . 137 11. 4 Summary.
. . . . . . . . . . . . . . . . . . . . . . . . . 139 References . . . .
. . . . . . . . . . . . . . . . . . . . . . . . 139 ix 12 SPECIAL CASES
OF HARD PROBLEMS 141 12. 1 Problem Statement 142 12. 2 Logic Simulation
143 12. 3 Logic Circuit Modeling . 146 12. 3. 1 Modelfor a Boolean Gate
. . . . . . . . . . . . . 147 12. 3. 2 Circuit Modeling 148 12.
