The beta-assignment problem in general graphs

檔案

日期

1997-08-01

類型

期刊名稱

COMPUTERS & OPERATIONS RESEARCH

卷期與頁次

第 24 卷第 8 期,頁 757–765

ISSN

0305-0548

語言

英文

摘要

We study a variation of the assignment problem in operations research and formulate it in terms of graphs as follows. Suppose G=(V,E) is a graph and U a subset of V.! A beta-assignment of G with respect to U is an edge set X such that deg(X)(nu)=1 for all vertices nu in U, where deg(X)(nu) is the degree of nu in the subgraph of G induced by the edge set X. The beta-assignment problem is to find a beta-assignment X such that beta(X)=max {deg(X)(nu):nu is an element of V-U} is minimum. The purpose of this paper is to give an O(n(3))-time algorithm for the beta-assignment problem in general graphs. As byproducts, we also obtain a duality theorem as well as a necessary and sufficient condition for the existence of a beta-assignment for a general graph. The latter result is a generalization of Tutte's theorem for the existence of a perfect matching of a general graph. (C) 1997 Elsevier Science Ltd.

所屬典藏

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

引用此條目

Chang, G., & Ho, P. (1997). The beta-assignment problem in general graphs. COMPUTERS & OPERATIONS RESEARCH, 24(8), 757–765. https://ir.lib.nycu.edu.tw/handle/11536/402

BibTeX RIS

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

分享

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