Two-Path Subsets: Efficient Counting and Applications to Performability Analysis
| dc.contributor.author | Ball, Michael O. | en_US |
| dc.contributor.author | Hagstrom, Jane N. | en_US |
| dc.contributor.author | Provan, J. Scott | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T10:02:20Z | |
| dc.date.available | 2007-05-23T10:02:20Z | |
| dc.date.issued | 1996 | en_US |
| dc.description.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. | en_US |
| dc.format.extent | 1143593 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/5792 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1996-77 | en_US |
| dc.subject | network management | en_US |
| dc.subject | algorithms | en_US |
| dc.subject | combinatorics | en_US |
| dc.subject | computational complexity | en_US |
| dc.subject | graph theory | en_US |
| dc.subject | paths | en_US |
| dc.subject | enumeration | en_US |
| dc.subject | PERT | en_US |
| dc.subject | Intelligent Signal Processing | en_US |
| dc.subject | Communications Systems | en_US |
| dc.title | Two-Path Subsets: Efficient Counting and Applications to Performability Analysis | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1