The beta-assignment problem in general graphs
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
765 | en_US |
dc.citation.issue |
8 | en_US |
dc.citation.spage |
757 | en_US |
dc.citation.volume |
24 | en_US |
dc.citation.woscount |
2 | |
dc.contributor.author |
Chang, GJ | en_US |
dc.contributor.author |
Ho, PH | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2014-12-08T15:01:34Z | |
dc.date.available |
2014-12-08T15:01:34Z | |
dc.date.issued |
1997-08-01 | en_US |
dc.description.abstract |
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. | en_US |
dc.identifier.issn |
0305-0548 | en_US |
dc.identifier.journal |
COMPUTERS & OPERATIONS RESEARCH | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/402 | |
dc.identifier.wosnumber |
WOS:A1997XM29200007 | |
dc.language.iso |
en_US | en_US |
dc.title |
The beta-assignment problem in general graphs | en_US |
dc.type |
Article | en_US |
檔案
- A1997XM29200007.pdf (679.7 KB, Adobe PDF)
所屬典藏: 期刊論文