| Presentation | 2008-02-08 Comparison of exact solutions and greedy solutions in static test compaction Kei Yagisawa, Koji Yamazaki, Toshinori Hosokawa, Hisao Tamaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper, we formulate static test compaction using don't cares as a minimum clique cover problem and a vertex coloring problem. We made experiments on exact solution methods and greedy solution methods. For most test patterns used in this experiment, the upper and lower bounds are close to the exact solution. This holds for wide variety of test generation methods. We coclude that greedy solutions are very close to exact solutions and there is small advantage in computing exact solutions for many circuits. Moreover, we indicate the subset of test patterns which is a bottleneck of test compaction, and consider the way to improve the compaction efficiency. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Static Compaction / Minimum Clique Cover / Maximum Independent Sets |
| Paper # | DC2007-79 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2008/2/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Dependable Computing (DC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Comparison of exact solutions and greedy solutions in static test compaction |
| Sub Title (in English) | |
| Keyword(1) | Static Compaction |
| Keyword(2) | Minimum Clique Cover |
| Keyword(3) | Maximum Independent Sets |
| 1st Author's Name | Kei Yagisawa |
| 1st Author's Affiliation | Department of Science and Technology, Meiji University() |
| 2nd Author's Name | Koji Yamazaki |
| 2nd Author's Affiliation | School of Information and Communication, Meiji University |
| 3rd Author's Name | Toshinori Hosokawa |
| 3rd Author's Affiliation | College of Industrial Technology, Nihon University |
| 4th Author's Name | Hisao Tamaki |
| 4th Author's Affiliation | Department of Science and Technology, Meiji University |
| Date | 2008-02-08 |
| Paper # | DC2007-79 |
| Volume (vol) | vol.107 |
| Number (no) | 482 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |