The beta-assignment problems

檔案

日期

1998-02-01

類型

期刊名稱

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

卷期與頁次

第 104 卷第 3 期,頁 593–600

ISSN

0377-2217

語言

英文

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chang, G., & Ho, P. (1998). The beta-assignment problems. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 104(3), 593–600. https://ir.lib.nycu.edu.tw/handle/11536/28

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/28