Presentation | 2006-09-26 Improved Algorithms K-LAG-V and K-LAG-VL for the Constrained Via Minimization Problem Jun NAGAI, Daisuke TAKAFUJI, Satoshi TAOKA, Toshimasa WATANABE, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The k-layer constrained via minimization problem (kCVM) is to find assignment of wire segments to k layers so that the number of vias is minimum, and is NP-hard even if k≧3. So, heuristic algorithms for kCVM are proposed, and it is known that K-LAG has the highest capability among those algorithms. The subject of this paper is to propose two heuristic algorithms K-LAG-V and K-LAG-VL that are enhanced versions of K-LAG. Based on experimental results, it is shown that proposed algorithms are useful for solving kCVM with k=4, 6, 8, 10 or 12. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Constrained via minimization problems / layer assignment / NP-hardness / heuristic algorithms |
Paper # | COMP2006-27 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2006/9/19(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 | Theoretical Foundations of Computing (COMP) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Improved Algorithms K-LAG-V and K-LAG-VL for the Constrained Via Minimization Problem |
Sub Title (in English) | |
Keyword(1) | Constrained via minimization problems |
Keyword(2) | layer assignment |
Keyword(3) | NP-hardness |
Keyword(4) | heuristic algorithms |
1st Author's Name | Jun NAGAI |
1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
2nd Author's Name | Daisuke TAKAFUJI |
2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
3rd Author's Name | Satoshi TAOKA |
3rd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
4th Author's Name | Toshimasa WATANABE |
4th Author's Affiliation | Graduate School of Engineering, Hiroshima University |
Date | 2006-09-26 |
Paper # | COMP2006-27 |
Volume (vol) | vol.106 |
Number (no) | 258 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |