Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T09:04:28.541Z Has data issue: false hasContentIssue false
  • English
  • Français

THE TREE CUT AND MERGE ALGORITHM FOR ESTIMATION OF NETWORK RELIABILITY

Published online by Cambridge University Press:  07 January 2003

K.-P. Hui ,
N. Bean ,
M. Kraetzl  and
D. Kroese
K.-P. Hui
Affiliation:
Information Networks Division, DSTO, Edinburgh 5111, Australia, E-mail: [email protected]
N. Bean
Affiliation:
Department of Applied Mathematics, University of Adelaide, Adelaide 5005, Australia, E-mail: [email protected]
M. Kraetzl
Affiliation:
ISR Division, DSTO, Edinburgh 5111, Australia, E-mail: [email protected]
D. Kroese
Affiliation:
Department of Mathematics, University of Queensland, Brisbane 4072, Australia, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This article presents Monte Carlo techniques for estimating network reliability. For highly reliable networks, techniques based on graph evolution models provide very good performance. However, they are known to have significant simulation cost. An existing hybrid scheme (based on partitioning the time space) is available to speed up the simulations; however, there are difficulties with optimizing the important parameter associated with this scheme. To overcome these difficulties, a new hybrid scheme (based on partitioning the edge set) is proposed in this article. The proposed scheme shows orders of magnitude improvement of performance over the existing techniques in certain classes of network. It also provides reliability bounds with little overhead.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 17 , Issue 1 , January 2003 , pp. 23 - 45
Copyright
© 2003 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)