ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
59 | en_US |
dc.citation.issue |
1 | en_US |
dc.citation.spage |
55 | en_US |
dc.citation.volume |
53 | en_US |
dc.citation.woscount |
0 | |
dc.contributor.author |
CHANG, YC | en_US |
dc.contributor.author |
HSU, LH | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:03:34Z | |
dc.date.available |
2014-12-08T15:03:34Z | |
dc.date.issued |
1995-01-13 | en_US |
dc.description.abstract |
Let G = (V,E) be a graph. We associate with each edge e(i) is an element of E an ordered pair of rational numbers (a(i), b(i)). Let the weight of a spanning tree T, w(T), be defined as Sigma(ei is an element of T) a(i) + Pi(ei is an element of T) b(i). A spanning tree T in G is called a w-optimum spanning tree if w(T) greater than or equal to w(T') for all spanning trees T' in G. The function w is one instance in a class of two-parameter objectives. Hassin and Tamir proposed a unified approach for solving the class of two-parameter objective optimum spanning tree problems. Let s be an objective in the class and F-s(G) denote the weight of the s-optimum spanning tree of G. The element perturbation problem of the s-optimum spanning tree is to compute F-s(G - e(k)) for all e(k) is an element of E. With Hassin and Tamir's approach, let t(s)(p, q) be the complexity of computing the s-optimum spanning tree where p = V and q = E. In this paper, we present an approach to solve the element perturbation problem of the s-optimum spanning tree in t(s)(p, q). | en_US |
dc.identifier.issn |
0020-0190 | en_US |
dc.identifier.journal |
INFORMATION PROCESSING LETTERS | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/2103 | |
dc.identifier.wosnumber |
WOS:A1995QA31100009 | |
dc.language.iso |
en_US | en_US |
dc.subject |
COMBINATORIAL ALGORITHMS | en_US |
dc.subject |
COMPLEXITY | en_US |
dc.subject |
SPANNING TREES | en_US |
dc.subject |
MATROID | en_US |
dc.title |
ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES | en_US |
dc.type |
Article | en_US |
檔案
- A1995QA31100009.pdf (463.4 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
CHANG, Y., & HSU, L. (1995). ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES. INFORMATION PROCESSING LETTERS, 53(1), 55–59. https://ir.lib.nycu.edu.tw/handle/11536/2103
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/2103