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 X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.