A note on the bottleneck graph partition problem

B. Klinz, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)
    8 Downloads (Pure)


    The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem with running time O(n2), where n is the number of vertices in the graph. Our result answers an open problem posed in a recent paper by Hochbaum and Pathria (1996).
    Original languageEnglish
    Pages (from-to)189-191
    Number of pages3
    Issue number3
    Publication statusPublished - 1999


    Dive into the research topics of 'A note on the bottleneck graph partition problem'. Together they form a unique fingerprint.

    Cite this