Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

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
  • Published: 30/04/1994

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.

Information
Guidelines
CP Initiatives
Follow CP
Facebook Twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
FE. Shahrokhi, L. A. Székelyt. The Complexity of the Bottleneck Graph Bipartition Problem[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 015. 221-226. DOI: .