• English
    • Norsk
  • English 
    • English
    • Norsk
  • Administration
View Item 
  •   Home
  • Det matematisk-naturvitenskapelige fakultet
  • Institutt for informatikk
  • Institutt for informatikk
  • View Item
  •   Home
  • Det matematisk-naturvitenskapelige fakultet
  • Institutt for informatikk
  • Institutt for informatikk
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A study of different matching heuristics

Martinsen, Jan Kasper
Master thesis
View/Open
No file.
Year
2005
Permanent link
http://urn.nb.no/URN:NBN:no-10557

Metadata
Show metadata
Appears in the following Collection
  • Institutt for informatikk [3603]
Abstract
A well-known combinatorial optimization problem is the graph partitioning problem. Since solving it optimally requires very much time, we have to settle for approximated methods. One such method is the multilevel k-way partitioning scheme. The overall idea is the following: The size of the graph is reduced during a process known as coarsening, where smaller and smaller graphs are made. Then a k-way partition is found from the much smaller graph and the graph and the partition is projected back to the original size.

In this master thesis, we study a central part of the multilevel k-way partitioning scheme, coarsening. In order make smaller and smaller graphs we use a technique known as matching. We introduce a new matching heuristic, global greedy heavy edge matching and perform a large number of experiments comparing it to other matching heuristics.

Our results include the discovery of two new partition vectors for the

graph partitioning archive(http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/), and that using global greedy heavy edge matching generally produces better results than already existing matching heuristics.
 
Responsible for this website 
University of Oslo Library


Contact Us 
duo-hjelp@ub.uio.no


Privacy policy
 

 

For students / employeesSubmit master thesisAccess to restricted material

Browse

All of DUOCommunities & CollectionsBy Issue DateAuthorsTitlesThis CollectionBy Issue DateAuthorsTitles

For library staff

Login
RSS Feeds
 
Responsible for this website 
University of Oslo Library


Contact Us 
duo-hjelp@ub.uio.no


Privacy policy