Filtern
Erscheinungsjahr
- 2019 (1)
Dokumenttyp
- ZIB-Report (1)
Sprache
- Englisch (1) (entfernen)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Institut
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.