Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    •   DRUM
    • A. James Clark School of Engineering
    • Institute for Systems Research Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Threshold Reliability of Networks with Small Failure Sets

    Thumbnail
    View/Open
    TR_93-43.pdf (1.479Mb)
    No. of downloads: 433

    Date
    1993
    Author
    Ball, Michael O.
    Hagstrom, Jane N.
    Provan, J. Scott
    Metadata
    Show full item record
    Abstract
    This paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. For the network flow model we are given a capacitated source/sink graph in which arcs fail randomly. The system is defined as operating whenever the max-flow value is greater than a threshold. For the project scheduling model we are given a directed acyclic source/sink graph in which each arc has two lengths. Each arc randomly takes on one of two states. In the "operating" state it takes on its smaller length and in its "failed" state it takes on it larger length. The system is defined as operating whenever the length of the longest path is less than a threshold. We address a special case of the threshold flow problem in which all arcs have the same capacity and a special case of the project scheduling model in which the difference between the lower and higher arc lengths is constant. For these special cases we show that if the underlying systems are 1-critical, namely, all arcs are in some cutset of size two, then the threshold flow problem can be solved in polynomial time and planar project scheduling problem can be solved in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path. We also show how the basic approach can be used to generate bounds for systems that are "almost critical".
    URI
    http://hdl.handle.net/1903/5388
    Collections
    • Institute for Systems Research Technical Reports

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility