The Complexity of the Bottleneck Graph Bipartition Problem

FE. Shahrokhi1, L. A. Székelyt2,2
1Department of Computer Science University of North Texas Denton, Texas, 76203
2Institut fiir Okonometrie und Operations Research Rheinische Friedrich-Wilhelms Universitat 5300 Bonn, Germany

Abstract

In this paper, we prove the NP-hardness of the bottleneck graph bipartition problem and study the complexity status of possible approximation algorithms for some related problems.