License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.1
URN: urn:nbn:de:0030-drops-89368
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8936/
Go to the corresponding LIPIcs Volume Portal

Heuer, Tobias ; Sanders, Peter ; Schlag, Sebastian

Network Flow-Based Refinement for Multilevel Hypergraph Partitioning

pdf-format:
LIPIcs-SEA-2018-1.pdf (3 MB)

Abstract

We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a k-way partition. The framework generalizes the flow-based improvement algorithm of KaFFPa from graphs to hypergraphs and is integrated into the hypergraph partitioner KaHyPar. By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas while still having a running time comparable to that of hMetis.

BibTeX - Entry

@InProceedings{heuer_et_al:LIPIcs:2018:8936,
  author =	{Tobias Heuer and Peter Sanders and Sebastian Schlag},
  title =	{{Network Flow-Based Refinement for Multilevel Hypergraph Partitioning}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{1:1--1:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8936},
  URN =		{urn:nbn:de:0030-drops-89368},
  doi =		{10.4230/LIPIcs.SEA.2018.1},
  annote =	{Keywords: Multilevel Hypergraph Partitioning, Network Flows, Refinement}
}

Keywords: Multilevel Hypergraph Partitioning, Network Flows, Refinement
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

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