Reliability of communication networks with delay constraints: computational complexity and complete topologies
Let G=(V,E) be a graph with a distinguished set of terminal vertices K⫅V. We define the K-diameter of G as the maximum distance between any pair of vertices of K. If the edges fail randomly and independently with known probabilities (vertices are always operational), the diameter-constrained K-termi...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2004-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/S016117120430623X |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850167199391547392 |
|---|---|
| author | H. Cancela L. Petingi |
| author_facet | H. Cancela L. Petingi |
| author_sort | H. Cancela |
| collection | DOAJ |
| description | Let G=(V,E) be a graph with a distinguished set of terminal
vertices K⫅V. We define the K-diameter of G as
the maximum distance between any pair of vertices of K. If the
edges fail randomly and independently with known probabilities
(vertices are always operational), the
diameter-constrained K-terminal reliability of G,
RK(G,D), is defined as the probability that surviving edges
span a subgraph whose K-diameter does not exceed D. In general, the computational complexity
of evaluating RK(G,D) is NP-hard, as this measure subsumes the
classical K-terminal reliability RK(G), known to belong to
this complexity class. In this note, we show that even though for
two terminal vertices s and t
and D=2, R{s,t}(G,D)
can be determined in polynomial time, the problem of calculating
R{s,t}(G,D) for fixed values of D, D≥3, is
NP-hard. We also generalize this result for any fixed number of
terminal vertices. Although it is very unlikely that general
efficient algorithms exist, we present a recursive formulation
for the calculation of R{s,t}(G,D) that yields a
polynomial time evaluation algorithm in the case of complete
topologies where the edge set can be partitioned into at most
four equi-reliable classes. |
| format | Article |
| id | doaj-art-e269666981f24bf48fe1e1e4a58377f8 |
| institution | OA Journals |
| issn | 0161-1712 1687-0425 |
| language | English |
| publishDate | 2004-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Mathematics and Mathematical Sciences |
| spelling | doaj-art-e269666981f24bf48fe1e1e4a58377f82025-08-20T02:21:14ZengWileyInternational Journal of Mathematics and Mathematical Sciences0161-17121687-04252004-01-012004291551156210.1155/S016117120430623XReliability of communication networks with delay constraints: computational complexity and complete topologiesH. Cancela0L. Petingi1Instituto de Computación, Facultad de Ingeniería, Universidad de la República, J. Herrera y Reissig 565, Montevideo 11300, UruguayComputer Science Department, College of Staten Island, City University of New York, 2800 Victory Boulevard, Staten Island, 10314, NY, USALet G=(V,E) be a graph with a distinguished set of terminal vertices K⫅V. We define the K-diameter of G as the maximum distance between any pair of vertices of K. If the edges fail randomly and independently with known probabilities (vertices are always operational), the diameter-constrained K-terminal reliability of G, RK(G,D), is defined as the probability that surviving edges span a subgraph whose K-diameter does not exceed D. In general, the computational complexity of evaluating RK(G,D) is NP-hard, as this measure subsumes the classical K-terminal reliability RK(G), known to belong to this complexity class. In this note, we show that even though for two terminal vertices s and t and D=2, R{s,t}(G,D) can be determined in polynomial time, the problem of calculating R{s,t}(G,D) for fixed values of D, D≥3, is NP-hard. We also generalize this result for any fixed number of terminal vertices. Although it is very unlikely that general efficient algorithms exist, we present a recursive formulation for the calculation of R{s,t}(G,D) that yields a polynomial time evaluation algorithm in the case of complete topologies where the edge set can be partitioned into at most four equi-reliable classes.http://dx.doi.org/10.1155/S016117120430623X |
| spellingShingle | H. Cancela L. Petingi Reliability of communication networks with delay constraints: computational complexity and complete topologies International Journal of Mathematics and Mathematical Sciences |
| title | Reliability of communication networks with delay constraints: computational complexity and complete topologies |
| title_full | Reliability of communication networks with delay constraints: computational complexity and complete topologies |
| title_fullStr | Reliability of communication networks with delay constraints: computational complexity and complete topologies |
| title_full_unstemmed | Reliability of communication networks with delay constraints: computational complexity and complete topologies |
| title_short | Reliability of communication networks with delay constraints: computational complexity and complete topologies |
| title_sort | reliability of communication networks with delay constraints computational complexity and complete topologies |
| url | http://dx.doi.org/10.1155/S016117120430623X |
| work_keys_str_mv | AT hcancela reliabilityofcommunicationnetworkswithdelayconstraintscomputationalcomplexityandcompletetopologies AT lpetingi reliabilityofcommunicationnetworkswithdelayconstraintscomputationalcomplexityandcompletetopologies |