Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Author: search.filters.author.Ball, Michael O.Subject: search.filters.subject.graph theory

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Two-Path Subsets: Efficient Counting and Applications to Performability Analysis
    (1996) Ball, Michael O.; Hagstrom, Jane N.; Provan, J. Scott; ISR
    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.
  • Thumbnail Image
    Item
    Network Reliability
    (1992) Ball, Michael O.; Colbourn, Charles J.; Provan, J.S.; ISR
    This paper provides a detailed review of the state of the art in the field of network reliability analysis. The primary model treated is a stochastic network in which arcs fail randomly and independently with known failure probabilities. The inputs to the basic network reliability analysis problem consist of the network and a failure probability for each are in the network. The output is some measure of the reliability of the network. The reliability measures treated most extensively in this paper are: the two terminal measure, the probability that there exists a path between two specified nodes; the all-terminal measure the probability that the network is connected and the k-terminal measure, the probability that a specified node subset, K, is connected. In all cases the results concerning each problem's computational complexity, exact algorithms, analytic bounds and Monte Carlo methods are covered. The paper also treats more complex reliability measures including performability measures and stochastic shortest path, max flow and PERT problems. A discussion is provided on applications and using the techniques covered in practice.