Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Remarks on Invariant Method of the Second-Order Linear Differential Equations with Variable Coefficients Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Algorithmic Tile Self-Assembly for Solving the Maximal Matching Problem

Authors : Zhen Cheng, Yufang Huang, Jianhua Xiao

Published in: Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The maximal matching problem is a classic combinatorial optimization problem. Recently, computation by algorithmic tile self-assembly is proved to be a promising technique in nanotechnology, and this computational model is also demonstrated to be Turing universal. In this paper, the process of tile self-assembly model which is used to solve the maximal matching problem is shown including three operations: nondeterministic guess operation, AND operation and comparing operation. Our method can be performed this problem in Θ(mn) steps, here m and n is the number of edges and vertices of the given graph respectively.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Footplant Detection Based on Adjusting the Foot Height Threshold Automatically
next chapter Application of FDTD and Harmony Search Algorithm for Inverse Scattering Problem
Literature
1.
Adleman LM (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021–1024CrossRef
2.
Pan LQ, Liu GW, Xu J (2004) Solid phase based DNA solution of the coloring problem. Prog Nat Sci 14:104–107MathSciNet
3.
4.
Seeman NC (1998) DNA nanotechnology: novel DNA constructions. Annu Rev Biophy Biomol Struct 27:225–248CrossRef
5.
Mao C, Sun W, Seeman NC (1999) Designed two dimensional DNA Holliday junction arrays visualized by atomic force microscopy. J Am Chem Soc 121:5437–5443CrossRef
6.
Barish R, Rothemund PW, Winfree E (2005) Two computational primitives for algorithmic self-assembly: copying and counting. Nano Lett 12:2586–2592CrossRef
7.
Lo PK, Metera KL, Sleiman HF (2010) Self-assembly of three-dimensional DNA nanostructures and potential biological applications. Curr Opin Chem Biol 14:597–607CrossRef
8.
Wang H (1961) Proving theorems by pattern recognition. I. Bell Syst Tech J 40:1–42CrossRef
9.
Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, Caltech, Pasadena, CA
10.
Rothemund P, Winfree E (2000) The program-size complexity of self-assembled squares. In: Proceedings of the annual ACM symposium on theory of computing, Portland, USA, pp 459–468, May 21–23
11.
Fujibayashi K, Murata S (2009) Precise simulation model for DNA tile self-assembly. IEEE T Nanotechnol 8:361–368CrossRef
12.
13.
Reif JH, Sahu S, Yin P (2011) Complexity of graph self-assembly in accretive systems and self-destructible systems. Theor Comput Sci 412:1592–1605MathSciNetCrossRefMATH
14.
Cardinal J, Labbe M, Langerman S et al (2005) A tight analysis of the maximal matching heuristic. Lect Notes Comput Sci 3595:701–709MathSciNetCrossRefMATH
15.
Ding X, Yin ZX, Wang Y (2010) A DNA algorithm for maximal matching problem. International conference on bio-inspired computing: theories and applications, Beijing, China, pp 143–147
Metadata
Title
Algorithmic Tile Self-Assembly for Solving the Maximal Matching Problem
Authors
Zhen Cheng
Yufang Huang
Jianhua Xiao
Copyright Year
2013
Publisher
Springer Berlin Heidelberg
Book
Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013

Print ISBN: 978-3-642-37501-9

Electronic ISBN: 978-3-642-37502-6

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-3-642-37502-6_100

Premium Partner

    Image Credits