A DNA-based graph encoding scheme with its applications to graph isomorphism problems

DOI10.1016/j.amc.2008.04.041zbMath1228.68020OpenAlexW1971519785MaRDI QIDQ2378959

Sun-Yuan Hsieh, Hsin-Hung Chou, Chao-Wen Huang

Publication date: 14 January 2009

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2008.04.041

zbMATH Keywords

NP-completemolecular computingDNA-based computingbiological operationsDNA-based algorithmsthe maximum common subgraph problemthe subgraph isomorphism problem

Mathematics Subject Classification ID

Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Protein sequences, DNA sequences (92D20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

A computational DNA solution approach for the quadratic Diophantine equation ⋮ The domination numbers of cylindrical grid graphs ⋮ Linear-time compression of 2-manifold polygon meshes into information-theoretically optimal number of bits ⋮ Comparing large-scale graphs based on quantum probability theory ⋮ A polynomial-time DNA computing solution for the bin-packing problem

Cites Work

• Using sticker to solve the 3-dimensional matching problem in molecular supercomputers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A DNA-based graph encoding scheme with its applications to graph isomorphism problems