In classic optimization theory, the concept of stability refers to the study of how much and in which way the optimal solutions of a given minimization problem Π can vary as a function of small perturbations of the input data. Motivated by congestion problems arising in shortest-path based communication networks, in this paper we restrict ourselves to the case in which Π is actually a network design problem on a given graph G = (V,E,w) of |V| = n nodes, |E| = m edges, and with a positive real weight w(e) on each edge e ∈ E. We focus on a subclass of perturbations, that we call stretching perturbations, in which the weights of the edges of G can be increased by at most a fixed multiplicative real factor λ ≥ 1. For this class of perturbations, we address the problem of computing the stability number of any given subgraph H of G containing at least an optimal solution of Π, namely the maximum stretching factor for which H keeps on maintaining an optimal solution. Furthermore, given a stretching factor λ, we study the problem of constructing a minimal subgraph of G with stability number greater or equal to λ. We develop a general technique to solve both problems. By applying this technique to the minimum spanning tree and the single-source shortest paths tree (SPT) problems, we obtain O(m alpha(m,n)) and O(mn(m+nlogn)) time algorithms, respectively, where alpha(·,·) is the functional inverse of Ackermann’s function. Furthermore, for the SPT problem, we show that if H coincides with the set of all optimal solutions, then the time complexity can be reduced to O(mn) . Finally, for the single-source single-destination shortest path problem, if the optimal solutions of the input instance happen to form a set of vertex-disjoint paths, and H coincides with this set, then we show that we can compute the stability number in O(mn+n^2 logn) time.
Bilò, D., Gatto, M., Guala', L., Proietti, G., Widmayer, P. (2009). Stability of Networks in Stretchable Graphs. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Volume 5869 LNCS, 2010, Pages 100-112 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2009; Piran; Slovenia; 25 May 2009 through 27 May 2009; Code 79523. Springer International Publishing [10.1007/978-3-642-11476-2_9].
Stability of Networks in Stretchable Graphs
GUALA', LUCIANO;
2009-01-01
Abstract
In classic optimization theory, the concept of stability refers to the study of how much and in which way the optimal solutions of a given minimization problem Π can vary as a function of small perturbations of the input data. Motivated by congestion problems arising in shortest-path based communication networks, in this paper we restrict ourselves to the case in which Π is actually a network design problem on a given graph G = (V,E,w) of |V| = n nodes, |E| = m edges, and with a positive real weight w(e) on each edge e ∈ E. We focus on a subclass of perturbations, that we call stretching perturbations, in which the weights of the edges of G can be increased by at most a fixed multiplicative real factor λ ≥ 1. For this class of perturbations, we address the problem of computing the stability number of any given subgraph H of G containing at least an optimal solution of Π, namely the maximum stretching factor for which H keeps on maintaining an optimal solution. Furthermore, given a stretching factor λ, we study the problem of constructing a minimal subgraph of G with stability number greater or equal to λ. We develop a general technique to solve both problems. By applying this technique to the minimum spanning tree and the single-source shortest paths tree (SPT) problems, we obtain O(m alpha(m,n)) and O(mn(m+nlogn)) time algorithms, respectively, where alpha(·,·) is the functional inverse of Ackermann’s function. Furthermore, for the SPT problem, we show that if H coincides with the set of all optimal solutions, then the time complexity can be reduced to O(mn) . Finally, for the single-source single-destination shortest path problem, if the optimal solutions of the input instance happen to form a set of vertex-disjoint paths, and H coincides with this set, then we show that we can compute the stability number in O(mn+n^2 logn) time.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.