Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Chevalier, Cédric; Safro, Ilya License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-20820


Weighted aggregation for multi-level graph partitioning



Graph partitioning is a well-known optimization problem of great interest in theoretical and applied studies. Since the 1990s, many multilevel schemes have been introduced as a practical tool to solve this problem. A multilevel algorithm may be viewed as a process of graph topology learning at different scales in order to generate a better approximation for any approximation method incorporated at the uncoarsening stage in the framework. In this work we compare two multilevel frameworks based on the geometric and the algebraic multigrid schemes for the partitioning problem.

BibTeX - Entry

  author =	{Chevalier, C\'{e}dric and Safro, Ilya},
  title =	{{Weighted aggregation for multi-level graph partitioning}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-20820},
  doi =		{10.4230/DagSemProc.09061.21},
  annote =	{Keywords: Graph partitioning, multilevel, coarsening, weighted aggregation}

Keywords: Graph partitioning, multilevel, coarsening, weighted aggregation
Seminar: 09061 - Combinatorial Scientific Computing
Issue date: 2009
Date of publication: 24.07.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI