The week's pick
Random Articles
Reseach Article
Digital Circuit Layout based on Graph Partitioning Technique using DNA Computing
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 69 - Number 25 |
| Year of Publication: 2013 |
| Authors: Maninder Kaur, Kawaljeet Singh |
10.5120/12127-8397
|
Maninder Kaur, Kawaljeet Singh . Digital Circuit Layout based on Graph Partitioning Technique using DNA Computing. International Journal of Computer Applications. 69, 25 ( May 2013), 17-20. DOI=10.5120/12127-8397
Abstract
After Adleman and Lipton have described the potential power of DNA computing, researchers have developed an interest in DNA computing for solving difficult computational problems like NP-complete problems. Partitioning of digital circuits also come under this category. Partitioning plays a key role in the design of a computer system. Existing conventional methods are unable to achieve the required breakthrough in terms of complexity, time and cost. This paper discusses how the potential of DNA can be used to solve the instances of circuit partitioning problem in an efficient way. A prototypical algorithm named DBACP is developed for solving the partitioning problem which is compared with SCAP approach on the small scale instances of circuit Benchmarks.
References
- Alpert, C. J. , Kahng, A. , (1995). "Recent Developments in Netlist Partitioning: A survey", in Integration: the VLSI Journal, vol. 19, 1-18.
- Kumar, V. , Grama, A. , Gupta, A. , Karypis, G. , (1994), "Introduction to Parallel Computing. Design and analysis of algorithms", The Benjamin/Cummings Publishing company
- Garey, M. R. , Johnson, D. S. , (1979), "Computers and Interactability: A Guide to the Theory of NP-Completeness", W. H. Freeman & Company, San Francisco.
- http://vlsicad. ucsd. edu/GSRC/bookshelf/Slots/Partitioning/
- K. ,Maninder, S. , Kawaljeet (2011). "Soft Computing Approach for Digital Circuit Layout based on Graph Partitioning". International Journal of Computer Applications, Volume 15– No. 1.
- J. Watada and R. B. A. Barkar, "DNA computing and its applications," in Proc. 8th Int. Conf. Intell. Syst. Des. Appl. , Nov. 2008, pp. 288–294.
- J. Y. Lee, S. Y. Shin, T. H. Park, and B. -T. Zhang, "Solving traveling salesman problems with DNA molecules encoding numerical value," Biosystems, vol. 78, no. 1–3, pp. 39–47, Dec. 2004.
- Kahan, M. ; Gil, B. ; Adar, R. ; Shapiro, E. (2008). "Towards molecular computers that operate in a biological environment". Physica D: Nonlinear Phenomena 237 (9): 1165–1172.
- Fiducia, C. M. , and Mattheyses, R. M. , (1982),"A linear time heuristic for improving network partitioning", in Proc ACM/IEEE Design Automation, 175-181.
- Holland, J. , (1975), "Adaptation in Natural and Artificial Systems", Ann Arbor: University of Michigan Press.
- Kernighan, B. W. , Lin S. , (1970), "An Efficient Heuristic Procedure for Partitioning Graphs", the Bell Sys. Tech. Journal, 291-307.
- David Padua "Encyclopedia of Parallel Computing," Volume 4, 2011.
- S. Shin, I. Lee, D. Kim, and B. Zhang, "Multiobjective evolutionary optimization of DNA sequences for reliable DNA computing," IEEE Trans. Evol. Comput. , vol. 9, no. 2, pp. 143–158, Apr. 2005.
- M. Darehmiraki and H. M. Nehi, "Molecular solution to the 0–1 knapsack problem based on DNA computing," Appl. Math. Comput. , vol. 187, no. 2,pp. 1033–1037, 2007.
- Roweis, S. , Winfree, E. , Burgoyne, R. , Chelyapov, N. , Goodman, M. , Rothemund, P. , Adleman, L. , (1998), "A Sticker-Based Model for DNA Computation", Journal of Computational Biology, 4, 615-629.
Index Terms
Keywords