標題: The beta-assignment problems
作者: Chang, GJ
Ho, PH
應用數學系
Department of Applied Mathematics
關鍵字: assignment;bottleneck;augmenting path;label
公開日期: 1-二月-1998
摘要: Suppose G = (S, T, E) is a bipartite graph, where (S,T) is a bipartition of the vertex set. A beta-assignment is an edge set X subset of or equal to E such that deg(X)(i) = 1 for all i is an element of S. The cardinality beta-assignment problem is to find a beta-assignment X which minimizes beta(X) = max(j is an element of)T deg(X)(j). Suppose we associate every edge with a weight which is a real number. The bottleneck beta-assignment problem is to find a beta-assignment X that minimizes beta(X) and maximizes the minimum edge weight on X. The weighted beta-assignment problem is to find a beta-assignment X that minimizes beta(X) and maximizes the total weights of edges in X. This paper presents O(/SJ//E/)-time algorithms for the cardinality and the bottleneck beta-assignment problems and an O(/S/(2)/T/ + /S//T/(2))-time algorithm for the weighted beta-assignment problem. (C) 1998 Elsevier Science B.V.
URI: http://hdl.handle.net/11536/28
ISSN: 0377-2217
期刊: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume: 104
Issue: 3
起始頁: 593
結束頁: 600
顯示於類別:期刊論文


文件中的檔案:

  1. 000071147100016.pdf