Multi-level technique

Multi-level technique

In mathematics, the multi-level technique is a technique used to solve the graph partitioning problem.

The idea of the multi-level technique is to reduce the magnitude of a graph by merging vertices together, compute a partition on this reduced graph, and finally project this partition on the original graph.

In the first phase the magnitude of the graph is reduced by merging vertices. The merging of vertices is done iteratively: of a graph a new coarser graph is created and of this new coarser graph an even more coarse graph is created. This is done until a certain small magnitude is reached. Thus graphs with different magnitudes are induced.

In the second phase a parition of the graph with the smallest magnitude – the coarsest graph – is computed.

In the third and last phase the computed partition is iteratively projected back to the original graph. In each iteration a refinement heuristic is applied. The merging of vertices induces a map between vertices of a graph and vertices of its coarser graph which is used for the back projection. A rebalancing to insure the size of the partition may be needed since vertices not belonging to the same partition may be merged together.

The multi-level technique has shown to significantly improve the results, both in terms of quality and running time. Especially when used on heuristics considering the graph only locally, as the multi-level technique constitutes a more global view on the graph. [1]

References

  1. ^ G Karypis, V Kumar (1999). "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs". Siam Journal on Scientific Computing. http://glaros.dtc.umn.edu/gkhome/node/107. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • multi-level marketing — N UNCOUNT Multi level marketing is a marketing technique which involves people buying a product, then earning a commission by selling it to their friends. The abbreviation MLM is also used. ...multi level marketing schemes …   English dictionary

  • Level sensor — Level sensors are used to detect liquid level. The liquid to be measured can be inside a container or can be in its natural form (e.g. a river or a lake). The level measurement can be either continuous or point values. Continuous level sensors… …   Wikipedia

  • Multi-core — A multi core processor (or chip level multiprocessor, CMP) combines two or more independent cores into a single package composed of a single integrated circuit (IC), called a die, or more dies packaged together. The individual core is normally a… …   Wikipedia

  • Modern Technique of the Pistol — The Modern Technique of the Pistol is a method for using a handgun for self defense. The Modern Technique uses a two handed grip on the pistol and brings the weapon to eye level, so that the sights may be used to aim at one s target. This… …   Wikipedia

  • Micro-Threads (multi core) — Micro Threads for multi core and many cores processors is a mechanism to hide memory latency similar to multi threading architectures. However, it is done in software for multi core processors such as the Cell Broadband Engine to dynamically hide …   Wikipedia

  • Simultaneous Multi Threading — est une technique datant des années 1950. Elle consiste, comme le Symmetric multiprocessing (SMP), à augmenter le TLP (Thread Level Parallelism), c’est à dire le parallélisme des threads. Le but est d améliorer le remplissage du flot d… …   Wikipédia en Français

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • Distributed operating system — A distributed operating system is the logical aggregation of operating system software over a collection of independent, networked, communicating, and spatially disseminated computational nodes.[1] Individual system nodes each hold a discrete… …   Wikipedia

  • CPU cache — Cache memory redirects here. For the general use, see cache. A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the… …   Wikipedia

  • Flash memory — Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube Non volatile …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”