A Memory-efficient Bounding Algorithm for the Two-terminal Reliability Problem | Zendy

Minh Duc Le | Zendy; Max Walter | Zendy; Josef Weidendorfer | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Memory-efficient Bounding Algorithm for the Two-terminal Reliability Problem

Author(s) -

Minh Duc Le,

Max Walter,

Josef Weidendorfer

Publication year - 2013

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2012.11.015

Subject(s) - bounding overwatch , computer science , terminal (telecommunication) , limiting , algorithm , reliability (semiconductor) , extension (predicate logic) , auxiliary memory , graph , path (computing) , data structure , theoretical computer science , parallel computing , distributed computing , computer network , mechanical engineering , power (physics) , physics , quantum mechanics , artificial intelligence , computer hardware , engineering , programming language

The terminal-pair reliability problem, i.e. the problem of determining the probability that there exists at least one path of working edges connecting the terminal nodes, is known to be NP-hard. Thus, bounding algorithms are used to cope with large graph sizes. However, they still have huge demands in terms of memory. We propose a memory-efficient implementation of an extension of the Gobien-Dotson bounding algorithm. Without increasing runtime, compression of relevant data structures allows us to use low-bandwidth high-capacity storage. In this way, available hard disk space becomes the limiting factor. Depending on the input structures, graphs with several hundreds of edges (i.e. system components) can be handled

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research