What question did this study set out to answer?

This research aims to develop a polynomial algorithm for the k-cut problem, focusing on minimizing edge weights between nonempty graph components.

January 1, 1988

Polynomial algorithm for the k-cut problem

Key Points

This research aims to develop a polynomial algorithm for the k-cut problem, focusing on minimizing edge weights between nonempty graph components.
Developed a polynomial algorithm specifically for fixed values of k.
Analyzed the k-cut problem in the context of edge weighted graphs.
Explored the complexity related to arbitrary and fixed k.
Presented a polynomial algorithm that efficiently solves the k-cut problem for fixed k.
Demonstrated a significant reduction in computational complexity compared to existing NP-hard approaches.

Abstract

The k-cut problem is to find a partition of an edge weighted graph into k nonempty components, such that the total edge weight between components is minimum. This problem is NP-complete for arbitrary k and its version involving fixing a vertex in each component is NP hard even for k=3. A polynomial algorithm for the case of a fixed k is presented.>

Mark Helpful

Bookmark

Relay