research-article

Calculating two-terminal reliability in a diameter constrained network with cutnodes

Authors:

Denis A. Migov,

Olga K. RodionovaAuthors Info & Claims

ICUIMC '12: Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication

Article No.: 130, Pages 1 - 6

https://doi.org/10.1145/2184751.2184898

Published: 20 February 2012 Publication History

Get Access

Abstract

A network with reliable nodes and unreliable links is considered. Diameter constrained network reliability is defined as a probability that a set of terminals of a network are linked by operational paths with number of included edges less or equal to given integer. Calculation of diameter constrained network reliability is known to be NP-hard problem, as well as network probabilistic connectivity problem. Equations are presented that allows significant speeding up calculations in case of existing of one or more cutnodes.

References

[1]

Cancela H., Petingi L. Diameter constrained network reliability: exact evaluation by factorization and bound. Proc. of the International Conf. on Industrial Logistics, Japan, p. 359--366, 2001.

Google Scholar

[2]

Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and comlete topologies. International Journal of Mathematics and Mathematical Sciences. N 29, p. 1551--1562, 2004.

Crossref

Google Scholar

[3]

Cancela H., Petingi L. On the characterization of the domination of a diameter-constrained network reliability model. Discrete Applied Mathematics. vol. 154, p. 1885--1896, 2006.

Digital Library

Google Scholar

[4]

Cancela H., Petingi L. Properties of a generalized source-to-all network reliability model with diameter constraints. Omega. Vol. 35, p. 659--670, 2007.

Crossref

Google Scholar

[5]

Migov D. A., Rodionova O. K., Rodionov A. S., and Choo H. Network Probabilistic Connectivity: Using Node Cuts. EUC Worshops. Lecture Notes in Computer Science. Vol. 4097, p. 702--709, 2006.

Digital Library

Google Scholar

[6]

Colbourn Ch. J. The combinatorics of network reliability. New York: Oxford University Press, 160 P, 1987.

Digital Library

Google Scholar

[7]

Rodionova O. K., Rodionov A. S. and Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains. ICCSA--2004. Lecture Notes in Computer Science. Vol. 3046, p. 315--324, 2004.

Google Scholar

[8]

Carlier J., Lucet C. A decomposition algorithm for network reliability evaluation. Discrete Applied Mathematics. Vol. 65, n 3, p. 141--156, 1996.

Digital Library

Google Scholar

[9]

Moore E. F., Shannon C. E. Reliable circuits using less reliable relays. J. Franclin Inst., vol. 262, n. 4b. P. 191--208, 1956.

Google Scholar

[10]

Chen Y., Li J., and Chen J. A New Algorithm for Network Probabilistic Connectivity. Proc. of the Military Communications Conference. IEEE Press. Vol. 2, p. 920--923, 1999.

Google Scholar

[11]

Rodionov A. S., Choo H. On Generating Random Network Structures: Connected Graphs. ICCSA--2004. Lecture Notes in Computer Science. Vol. 3090, p. 483--491, 2004.

Google Scholar

Cited By

View all

Nesterov SMigov D(2017)Series-parallel transformation for diameter constrained network reliability computation2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)10.1109/SIBIRCON.2017.8109852(121-125)Online publication date: Sep-2017
https://doi.org/10.1109/SIBIRCON.2017.8109852
Nechunaeva KMigov DKim DKim SLee SHanzo LIsmail R(2015)Speeding up of genetic algorithm for network topology optimization with use of cumulative updating of network reliabilityProceedings of the 9th International Conference on Ubiquitous Information Management and Communication10.1145/2701126.2701163(1-4)Online publication date: 8-Jan-2015
https://dl.acm.org/doi/10.1145/2701126.2701163
Migov DShakhov V(2014)Reliability of Ad Hoc Networks with Imperfect NodesMultiple Access Communications10.1007/978-3-319-10262-7_5(49-58)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10262-7_5

Index Terms

Calculating two-terminal reliability in a diameter constrained network with cutnodes
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Recommendations

Decomposing graph with 2-node cuts for diameter constrained network reliability calculation
ICUIMC '13: Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication

We consider a network with unreliable communication channels and perfectly reliable nodes. The diameter constrained reliability for such a network is defined as a probability that a set of terminals of a network are linked by operational paths with ...
A recursive formula for the two-edge connected and biconnected reliability of a complete graph

The reliability polynomial RG,p of a finite undirected graph G=V,E gives the probability that the operational edges of G induce a connected graph assuming that all edges of G fail independently with identical probability q=1-p. In this article we ...
On the characterization of the domination of a diameter-constrained network reliability model
Special issue: Traces of the Latin American conference on combinatorics, graphs and applications: a selection of papers from LACGA 2004, Santiago, Chile

Let G = (V, E) be a digraph with a distinguished set of terminal vertices K ⊆ V and a vertex s ∈ K. We define the s, K-diameter of G as the maximum distance between s and any of the vertices of K. If the arcs fail randomly and independently with known ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICUIMC '12: Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication

February 2012

852 pages

ISBN:9781450311724

DOI:10.1145/2184751

Conference Chairs:
Suk-Han Lee
Sungkyunkwan University, Korea
,
Lajos Hanzo
University of Southampton, UK
,
Roslan Ismail
Universiti Kuala Lumpur, Malaysia
,
Program Chairs:
Dongsoo S. Kim
Indiana University
,
Min Young Chung
Sungkyunkwan University, Korea
,
Sang-Won Lee
Sungkyunkwan University, Korea

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 February 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Russian Foundation for Basic Research

Conference

ICUIMC '12

Sponsor:

SIGAPP
SKKU

ICUIMC '12: The 6th International Conference on Ubiquitous Information Management and Communication

February 20 - 22, 2012

Kuala Lumpur, Malaysia

Acceptance Rates

Overall Acceptance Rate 251 of 941 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
69
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nesterov SMigov D(2017)Series-parallel transformation for diameter constrained network reliability computation2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)10.1109/SIBIRCON.2017.8109852(121-125)Online publication date: Sep-2017
https://doi.org/10.1109/SIBIRCON.2017.8109852
Nechunaeva KMigov DKim DKim SLee SHanzo LIsmail R(2015)Speeding up of genetic algorithm for network topology optimization with use of cumulative updating of network reliabilityProceedings of the 9th International Conference on Ubiquitous Information Management and Communication10.1145/2701126.2701163(1-4)Online publication date: 8-Jan-2015
https://dl.acm.org/doi/10.1145/2701126.2701163
Migov DShakhov V(2014)Reliability of Ad Hoc Networks with Imperfect NodesMultiple Access Communications10.1007/978-3-319-10262-7_5(49-58)Online publication date: 2014
https://doi.org/10.1007/978-3-319-10262-7_5

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Decomposing graph with 2-node cuts for diameter constrained network reliability calculation

A recursive formula for the two-edge connected and biconnected reliability of a complete graph

On the characterization of the domination of a diameter-constrained network reliability model