du.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Use Multilevel Graph Partitioning Scheme to solve traveling salesman problem
Dalarna University, School of Technology and Business Studies, Computer Engineering.
2010 (English)Independent thesis Advanced level (degree of Master (Two Years))Student thesis
Abstract [en]

The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach. Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes. Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

Place, publisher, year, edition, pages
Borlange, 2010. , 53 p.
Keyword [en]
Multilevel Graph Partitioning
Identifiers
URN: urn:nbn:se:du-4910OAI: oai:dalea.du.se:4910DiVA: diva2:518928
Uppsok
Technology
Supervisors
Available from: 2010-08-27 Created: 2010-08-27 Last updated: 2012-04-24Bibliographically approved

Open Access in DiVA

fulltext(512 kB)741 downloads
File information
File name FULLTEXT01.pdfFile size 512 kBChecksum SHA-512
0605eb10f3bef35855e0d1d3160a20d4e736503e69a792cdcce61c5ceb6847e0f68d5381106630977a6b1247baefac448a8dd135b48cfba21ab2d0d1e2f05440
Type fulltextMimetype application/pdf

By organisation
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 741 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: 507 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf