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., Gualà, 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

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.
Structural Information and Communication Complexity, 16th International Colloquium, SIROCCO 2009
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
English
http://www.scopus.com/inward/record.url?eid=2-s2.0-77949428990&partnerID=40&md5=0e7a9d327921e43a6d02891214c3d7ca
Intervento a convegno
Bilò, D., Gatto, M., Gualà, 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].
Bilò, D; Gatto, M; Guala', L; Proietti, G; Widmayer, P
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/106714
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact