Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Approximating Balanced Graph Partitions

Please always quote using this URN: urn:nbn:de:0297-zib-73675
  • We consider the problem of partitioning a weighted graph into k connected components of similar weight. In particular, we consider the two classical objectives to maximize the lightest part or to minimize the heaviest part. For a partitioning of the vertex set and for both objectives, we give the first known approximation results on general graphs. Specifically, we give a $\Delta$-approximation where $\Delta$ is the maximum degree of an arbitrary spanning tree of the given graph. Concerning the edge partition case, we even obtain a 2-approximation for the min-max and the max-min problem, by using the claw-freeness of line graphs.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Ralf BorndörferORCiD, Ziena Elijazyfer, Stephan SchwartzORCiD
Document Type:ZIB-Report
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx)
Date of first Publication:2019/06/17
Series (Serial Number):ZIB-Report (19-25)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.