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.

    Two-Path Subsets: Efficient Counting and Applications to Performability Analysis

    Thumbnail
    View/Open
    TR_96-77.pdf (1.090Mb)
    No. of downloads: 435

    Date
    1996
    Author
    Ball, Michael O.
    Hagstrom, Jane N.
    Provan, J. Scott
    Metadata
    Show full item record
    Abstract
    The problem of computing preformability probabilities in stochastic PERT and flow networks is studied when the networks is ﲭinimally designed to withstand any two component failures. Polynomial-time algorithms to compute preformability when the network is planar -- the nonplanar versions being NP-hard -- solve related ﲴwo-path subset problems. Given an acyclic graph with weights on the arcs, the algorithms compute the total weight of all subsets of arcs that are contained in (1) two source-sink paths or (2) two arc-disjoint source-sink paths. A polynomial algorithm is given for (1), and for (2) in the case where the graph is a source-sink planar k-flow graph, that is edge-minimal with respect to supporting k units of flow.
    URI
    http://hdl.handle.net/1903/5792
    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