標題: The beta-assignment problem in general graphs
作者: Chang, GJ
Ho, PH
應用數學系
Department of Applied Mathematics
公開日期: 1-八月-1997
摘要: 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.
URI: http://hdl.handle.net/11536/402
ISSN: 0305-0548
期刊: COMPUTERS & OPERATIONS RESEARCH
Volume: 24
Issue: 8
起始頁: 757
結束頁: 765
顯示於類別:期刊論文


文件中的檔案:

  1. A1997XM29200007.pdf