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)

    Abstract

    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
    JournalNetworks
    Volume33
    Issue number3
    DOIs
    Publication statusPublished - 1999

    Cite this