A parametric maximum flow algorithm for bipartite graphs with applications

Y. L. Chen

doi:10.1016/0377-2217(93)E0161-P

A parametric maximum flow algorithm for bipartite graphs with applications

Y. L. Chen

Department of Information Management

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

Suppose we are given a capacitated bipartite network G with node sets S and T. In network G, the arc capacities are not fixed values but are functions of a single parameter λ, where λ is a continuous real variable. Our problem is to determine the minimum value of λ such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity O(nm² log(m/n)) is presented, where n is the number of nodes in S, m is the number of nodes in T and n ≤ m. Examples are then given to show how to use this parametric algorithm to solve practical problems.

Original language	English
Pages (from-to)	226-235
Number of pages	10
Journal	European Journal of Operational Research
Volume	80
Issue number	1
DOIs	https://doi.org/10.1016/0377-2217(93)E0161-P
State	Published - 5 Jan 1995

Keywords

Bipartite graph
Maximum flow
Parametric algorithm

Access to Document

10.1016/0377-2217(93)E0161-P

Cite this

@article{b56ffd936305410d955b4ba907336c57,

title = "A parametric maximum flow algorithm for bipartite graphs with applications",

abstract = "Suppose we are given a capacitated bipartite network G with node sets S and T. In network G, the arc capacities are not fixed values but are functions of a single parameter λ, where λ is a continuous real variable. Our problem is to determine the minimum value of λ such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity O(nm2 log(m/n)) is presented, where n is the number of nodes in S, m is the number of nodes in T and n ≤ m. Examples are then given to show how to use this parametric algorithm to solve practical problems.",

keywords = "Bipartite graph, Maximum flow, Parametric algorithm",

author = "Chen, {Y. L.}",

year = "1995",

month = jan,

day = "5",

doi = "10.1016/0377-2217(93)E0161-P",

language = "???core.languages.en_GB???",

volume = "80",

pages = "226--235",

journal = "European Journal of Operational Research",

issn = "0377-2217",

number = "1",

}

TY - JOUR

T1 - A parametric maximum flow algorithm for bipartite graphs with applications

AU - Chen, Y. L.

PY - 1995/1/5

Y1 - 1995/1/5

N2 - Suppose we are given a capacitated bipartite network G with node sets S and T. In network G, the arc capacities are not fixed values but are functions of a single parameter λ, where λ is a continuous real variable. Our problem is to determine the minimum value of λ such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity O(nm2 log(m/n)) is presented, where n is the number of nodes in S, m is the number of nodes in T and n ≤ m. Examples are then given to show how to use this parametric algorithm to solve practical problems.

AB - Suppose we are given a capacitated bipartite network G with node sets S and T. In network G, the arc capacities are not fixed values but are functions of a single parameter λ, where λ is a continuous real variable. Our problem is to determine the minimum value of λ such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity O(nm2 log(m/n)) is presented, where n is the number of nodes in S, m is the number of nodes in T and n ≤ m. Examples are then given to show how to use this parametric algorithm to solve practical problems.

KW - Bipartite graph

KW - Maximum flow

KW - Parametric algorithm

UR - http://www.scopus.com/inward/record.url?scp=0029636072&partnerID=8YFLogxK

U2 - 10.1016/0377-2217(93)E0161-P

DO - 10.1016/0377-2217(93)E0161-P

M3 - 期刊論文

AN - SCOPUS:0029636072

SN - 0377-2217

VL - 80

SP - 226

EP - 235

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -

A parametric maximum flow algorithm for bipartite graphs with applications

Abstract

Keywords

Access to Document

Fingerprint

Cite this