A note on the bottleneck graph partition problem

被引：0
|
作者：
Klinz, B [1 ]
Woeginger, GJ [1 ]
机构：
[1] Graz Univ Technol, Inst Math B, A-8010 Graz, Austria
来源：
NETWORKS | 1999年 / 33卷 / 03期
关键词：
D O I：
10.1002/(SICI)1097-0037(199905)33:3<189::AID-NET5>3.0.CO;2-2
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
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(n(2)), 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). (C) 1999 John Wiley & Sons, Inc.
引用
收藏
页码：189 / 191
页数：3
相关论文
共 50 条
  • [1] The bottleneck graph partition problem
    Hochbaum, DS
    Pathria, A
    NETWORKS, 1996, 28 (04) : 221 - 225
  • [2] A GRAPH PARTITION PROBLEM
    刘彦佩
    Acta Mathematicae Applicatae Sinica(English Series), 1996, (04) : 393 - 400
  • [3] A Graph Partition Problem
    Cioaba, Sebastian M.
    Cameron, Peter J.
    AMERICAN MATHEMATICAL MONTHLY, 2015, 122 (10): : 972 - 982
  • [4] A note on a cycle partition problem
    Yang, Fengli
    Vumar, Elkin
    APPLIED MATHEMATICS LETTERS, 2011, 24 (07) : 1181 - 1184
  • [5] A note on the complexity of the bilevel bottleneck assignment problem
    Fischer, Dennis
    Muluk, Komal
    Woeginger, Gerhard J.
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2022, 20 (04): : 713 - 718
  • [6] A note on the complexity of the bilevel bottleneck assignment problem
    Dennis Fischer
    Komal Muluk
    Gerhard J. Woeginger
    4OR, 2022, 20 : 713 - 718
  • [7] A NOTE ON DUAL TRAIL PARTITION OF A PLANE GRAPH
    UENO, S
    TSUJI, K
    KAJITANI, Y
    IEICE TRANSACTIONS ON COMMUNICATIONS ELECTRONICS INFORMATION AND SYSTEMS, 1991, 74 (07): : 1915 - 1917
  • [8] A note on the computational complexity of graph vertex partition
    Huang, Yuanqiu
    Chub, Yuming
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (03) : 405 - 409
  • [9] A strong formulation for the graph partition problem
    Chopra, Sunil
    Shim, Sangho
    NETWORKS, 2020, 75 (02) : 183 - 202
  • [10] A NOTE ON THE GRAPH AUGMENTATION PROBLEM
    UENO, S
    TSUJI, K
    KAJITANI, Y
    IEICE TRANSACTIONS ON COMMUNICATIONS ELECTRONICS INFORMATION AND SYSTEMS, 1991, 74 (04): : 679 - 680
12345