ELEMENT PERTURBATION PROBLEMS OF OPTIMUM SPANNING-TREES WITH 2-PARAMETER OBJECTIVES

Abstract

Let G = (V, E) be a graph. We associate with each edge ei E E an ordered pair of rational numbers (ni, bi). Let the weight of a spanning tree T, w(T), be defined as (Sigma(ei is an element of T) a(i))(2) + (Sigma(ei is an element of T) b(i))(2). A spanning tree T in G is called an optimum spanning tree if w(T) greater than or equal to w(T') for all spanning trees T' in G. The problem of finding the optimum spanning tree of the two-parameter objective is called MST2P. Hassin and Tamir have proposed an O(q(6)) algorithm for solving: MST2P, where q = E. Let f(G) denote the weight of the optimum spanning tree of G. The element perturbation problem of MST2P is to compute f(G - e(k)) for all e(k) is an element of E. In this paper, we present an O(q(6)) algorithm to solve the element perturbation problem of MST2P. Our algorithm can also be applied to the EPP of minimal cost/reliability ratio spanning tree problem in communication network design.