On the characterization of the source-to-all-terminal diameter-constrained reliability domination

Let G = (V;E) be a digraph with a distinguished set of terminal vertices K V and a vertex s 2 K . We de ne the s;K-diameter of G as the maximum distance between s and any of vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the D...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Cancela, Héctor, Petingi, Louis
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2003
Materias:
Ciencias Informáticas
Reliability
networks
diameter
domination
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/22636
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-22636
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Reliability
networks
diameter
domination
spellingShingle Ciencias Informáticas
Reliability
networks
diameter
domination
Cancela, Héctor
Petingi, Louis
On the characterization of the source-to-all-terminal diameter-constrained reliability domination
topic_facet Ciencias Informáticas
Reliability
networks
diameter
domination
description Let G = (V;E) be a digraph with a distinguished set of terminal vertices K V and a vertex s 2 K . We de ne the s;K-diameter of G as the maximum distance between s and any of vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the Diameter-constrained s;K-terminal reliability of G, Rs;K(G;D), is de ned as the probability that surviving arcs span a subgraph whose s;K- diameter does not exceed D [5, 11]. A graph invariant called the domination of a graph G was introduced by Satyanarayana and Prabhakar [13] to generate the non-canceling terms of the classical reliability expres- sion, Rs;K(G), based on the same reliability model (i.e. arcs fail randomly and indepen- dently and where nodes are perfect), and de ned as the probability that the surviving arcs span a subgraph of G with unconstrained nite s;K-diameter. This result allowed the generation of rapid algorithms for the computation of Rs;K(G). In this paper we present a characterization of the diameter-constrained s;K-terminal reliability domination of a digraph G = (V;E) with terminal set K = V , and for any diameter bound D, and, as a result, we solve the classical reliability domination, as a speci c case. Moreover we also present a rapid algorithm for the evaluation of Rs;V (G;D).
format Objeto de conferencia
Objeto de conferencia
author Cancela, Héctor
Petingi, Louis
author_facet Cancela, Héctor
Petingi, Louis
author_sort Cancela, Héctor
title On the characterization of the source-to-all-terminal diameter-constrained reliability domination
title_short On the characterization of the source-to-all-terminal diameter-constrained reliability domination
title_full On the characterization of the source-to-all-terminal diameter-constrained reliability domination
title_fullStr On the characterization of the source-to-all-terminal diameter-constrained reliability domination
title_full_unstemmed On the characterization of the source-to-all-terminal diameter-constrained reliability domination
title_sort on the characterization of the source-to-all-terminal diameter-constrained reliability domination
publishDate 2003
url http://sedici.unlp.edu.ar/handle/10915/22636
work_keys_str_mv AT cancelahector onthecharacterizationofthesourcetoallterminaldiameterconstrainedreliabilitydomination
AT petingilouis onthecharacterizationofthesourcetoallterminaldiameterconstrainedreliabilitydomination
bdutipo_str Repositorios
_version_ 1764820466156961793

Ejemplares similares