Solving the parametric bipartite maximum flow problem in unbalanced and closure bipartite graphs

被引：0
作者：
Ghiyasvand, Mehdi [1 ]
机构：
[1] Bu Ali Sina Univ, Dept Math, Fac Sci, Hamadan, Iran
来源：
ANNALS OF OPERATIONS RESEARCH | 2015年 / 229卷 / 01期
关键词：
Network flows; The parametric bipartite maximum flow problem; Closure graphs; Unbalanced bipartite graphs; Gallo et al's parametric maximum flow algorithm; SHOP SCHEDULING PROBLEMS; NETWORK FLOW; TIME-WINDOWS; ALGORITHMS;
D O I：
10.1007/s10479-015-1807-7
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Given a directed bipartite graph with a node set , and an arc set , where , , and . Chen (1995) presented an time algorithm to solve the parametric bipartite maximum flow problem. In this paper, we assume all arcs in have infinite capacity [such a graph is called closure graph Hochbaum (1998)], and present a new approach to solve the problem, which runs in time using Gallo et al's parametric maximum flow algorithm, see Gallo et al. (1989). In unbalanced bipartite graphs, we have , so, our algorithm improves Chens's algorithm in unbalanced and closure bipartite graphs.
引用
收藏
页码：397 / 408
页数：12
相关论文
共 28 条
123