CFP last date
20 January 2025
Reseach Article

Digital Circuit Layout based on Graph Partitioning Technique using DNA Computing

by Maninder Kaur, Kawaljeet Singh
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

@article{ 10.5120/12127-8397,
author = { Maninder Kaur, Kawaljeet Singh },
title = { Digital Circuit Layout based on Graph Partitioning Technique using DNA Computing },
journal = { International Journal of Computer Applications },
issue_date = { May 2013 },
volume = { 69 },
number = { 25 },
month = { May },
year = { 2013 },
issn = { 0975-8887 },
pages = { 17-20 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume69/number25/12127-8397/ },
doi = { 10.5120/12127-8397 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:31:36.243928+05:30
%A Maninder Kaur
%A Kawaljeet Singh
%T Digital Circuit Layout based on Graph Partitioning Technique using DNA Computing
%J International Journal of Computer Applications
%@ 0975-8887
%V 69
%N 25
%P 17-20
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Alpert, C. J. , Kahng, A. , (1995). "Recent Developments in Netlist Partitioning: A survey", in Integration: the VLSI Journal, vol. 19, 1-18.
  2. Kumar, V. , Grama, A. , Gupta, A. , Karypis, G. , (1994), "Introduction to Parallel Computing. Design and analysis of algorithms", The Benjamin/Cummings Publishing company
  3. Garey, M. R. , Johnson, D. S. , (1979), "Computers and Interactability: A Guide to the Theory of NP-Completeness", W. H. Freeman & Company, San Francisco.
  4. http://vlsicad. ucsd. edu/GSRC/bookshelf/Slots/Partitioning/
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. Fiducia, C. M. , and Mattheyses, R. M. , (1982),"A linear time heuristic for improving network partitioning", in Proc ACM/IEEE Design Automation, 175-181.
  10. Holland, J. , (1975), "Adaptation in Natural and Artificial Systems", Ann Arbor: University of Michigan Press.
  11. Kernighan, B. W. , Lin S. , (1970), "An Efficient Heuristic Procedure for Partitioning Graphs", the Bell Sys. Tech. Journal, 291-307.
  12. David Padua "Encyclopedia of Parallel Computing," Volume 4, 2011.
  13. 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.
  14. 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.
  15. 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

Computer Science
Information Sciences

Keywords

Memory Strands Extraction Crossover Mutation