Change search
ReferencesLink to record
Permanent link

Direct link
Improvements of a numerical Algorithm for a certain Class of Colouring Problems
Norwegian University of Science and Technology, Faculty of Natural Sciences and Technology, Department of Physics.
2014 (English)MasteroppgaveStudent thesis
Abstract [en]

We re-derive an algorithm used to calculate solutions for the edge-colouring and dimer problems for planar graphs. The theoretical background for this includes Pfaffian and then as Grassmann Integrals. We develop a new algorithm which is slightly faster and not restricted to planar graphs, and use this new algorithm to find results for small square, hexagonal and kagome grids. The new algorithm is generalised to a larger class of counting problems. Vi forklarer en algoritme for å finne løsninger til dimer- of kant-fargeleggingsproblemet for flate grafer. Den teoretiske bakgrunnen for algoritmen inkluderer Pfaffianen og Grassmann integraler. Vi lager en ny algoritme som er litt raskere og fungerer utenom flate grafer, og bruker denne for å finne resultater for firkant, sekskant of kagome gitre. Den nye algoritmen blir generalisert til en sto rre klasse telle problem.

Place, publisher, year, edition, pages
Institutt for fysikk , 2014. , 42 p.
Keyword [no]
ntnudaim:8513, MFY Fysikk
URN: urn:nbn:no:ntnu:diva-24823Local ID: ntnudaim:8513OAI: diva2:721831
Available from: 2014-06-05 Created: 2014-06-05

Open Access in DiVA

fulltext(663 kB)292 downloads
File information
File name FULLTEXT01.pdfFile size 663 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(224 kB)0 downloads
File information
File name COVER01.pdfFile size 224 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Physics

Search outside of DiVA

GoogleGoogle Scholar
Total: 292 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link