标题: | ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES |
作者: | CHANG, YC HSU, LH 资讯工程学系 Department of Computer Science |
关键字: | COMBINATORIAL ALGORITHMS;COMPLEXITY;SPANNING TREES;MATROID |
公开日期: | 13-一月-1995 |
摘要: | 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). |
URI: | http://hdl.handle.net/11536/2103 |
ISSN: | 0020-0190 |
期刊: | INFORMATION PROCESSING LETTERS |
Volume: | 53 |
Issue: | 1 |
起始页: | 55 |
结束页: | 59 |
显示于类别: | Articles |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.