nach oben

Journal of Combinatorial Optimization

Erschienen in:

21.09.2015

Code for polyomino and computer search of isospectral polyominoes

verfasst von: Xiaodong Liang, Rui Wang, Ji xiang Meng

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A new code, binary 2-dimentional code (B2DC), is proposed for polyominoes. An algorithm based on the B2DC and the reverse search method are proposed for enumerating nonisomorphic planar simply connected polyominoes. An enumeration tree and a new father-son relationship are defined for enumerating polyominoes. Then we propose an algorithm to build adjacent matrices and laplacian matrices by B2DCs of polyominoes and search isospectral polyomino graphs by computing characteristic polynomials of those matrices.

Vorheriger Artikel Neighbor product distinguishing total colorings

Nächster Artikel Total coloring of planar graphs without adjacent short cycles

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Avis D, Fukuda K (1996) Reverse search for enumeration. Discret Appl Math 65:21–46MathSciNetCrossRefMATH

Babić D, Gutman I (1992) On isospectral benzenoid graphs. J Math Chem 9:261–278CrossRef

Babić D (1993) Isospectral benzenoid graphs with an odd number of vertices. J Math Chem 12:137–146MathSciNetCrossRef

Caporossi G, Hansen P (1998) Enumeration of Polyhex Hydrocarbons to h=21. J Chem Inf Comput Sci 38:610–619CrossRef

Cioslowski J (1991) A conjecture on benzenoid graphs. J Math Chem 6:111–111CrossRef

Conway AR (1995) Enumerating 2D percolation series by the finite lattice method. J Phys A Math Gen 28:335–349CrossRefMATH

Conway AR, Guttmann AJ (1995) On two-dimensional percolation. J Phys A Math Gen 28:891–904CrossRefMATH

Golomb S (1994) Polyominoes: puzzles, patterns, problems and packings, Second edn. Princeton University Press, PrincetionMATH

Gutman I, Marković S, Grbović V (1991) The smallest pair of isospectral benzenoid systems. J Serb Chem Soc 56:553–554

Hansen P, Lebatteux C, Zheng M (1996) The boundary-edges code for polyhexes. Theochem J Mol Struct 363:237–247CrossRef

Harary F, Palmer E (1973) Graphical enumeration. Academic Press, New YorkMATH

Jensen I (2001) Enumerations of lattice animals and trees. J Stat Phys 102:865–881MathSciNetCrossRefMATH

Jensen I, Guttmann AJ (2000) Statistics of lattice animals (polyominoes) and polygons. J Phys A 33:L257–L263MathSciNetCrossRefMATH

Jensen I (2003) Counting polyominoes: a parallel implementation for cluster computing. LNCS 2659:203–212

Liang X, Meng J (2011) Computer search for isospectral benzenoid graphs. MATCH Commun Math Comput Chem 65:427–430MathSciNetMATH

Mertens S (1990) Lattice animals: A fast enumeration algorithm and new perimeter polynomials. J Stat Phys 58:1095–1108MathSciNetCrossRef

Oliveira e Silva T (2015) http://sweet.ua.pt/tos/animals/a44.html. Accessed 19 Dec 2014

Redelmeier DH (1981) Counting polyominoes: yet another attack. Discret Math 36:191–203MathSciNetCrossRefMATH

Zheng S, Wang Z, Zhang J, Xin X (1996) A result of searching for isospectral benzenoid graphs. J Xinjiang Univ (Nat Sci Ed) 13:21,28

Titel: Code for polyomino and computer search of isospectral polyominoes
verfasst von: Xiaodong Liang
Rui Wang
Ji xiang Meng
Publikationsdatum: 21.09.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9953-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2017

On the difference of two generalized connectivities of a graph

A linear-time algorithm for clique-coloring problem in circular-arc graphs

Total coloring of planar graphs without adjacent short cycles

A solution to a conjecture on the generalized connectivity of graphs

Neighbor product distinguishing total colorings

On the b-coloring of tight graphs

Premium Partner