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.
| 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) |
| ISSN: | 1438-0064 |
