## Abstract

Various network reliability problems are #P-complete, however, certain classes of networks such as series-parallel networks, admit polynomial time algorithms. We extend these efficient methods to a superclass of series-parallel networks, the partial 2-trees. In fact, we solve a more general problem: given a probabilistic partial 2-tree and a set T of target nodes, we compute in linear time the probability of obtaining a subgraph connecting all of the target nodes. Equivalently, this is the probability of obtaining a Steiner tree for T. The algorithm exploits a characterization of partial 2-trees as graphs with no subgraph homeomorphic to K_{4}.

Original language | English (US) |
---|---|

Pages (from-to) | 837-840 |

Number of pages | 4 |

Journal | Microelectronics Reliability |

Volume | 23 |

Issue number | 5 |

DOIs | |

State | Published - 1983 |

Externally published | Yes |

## ASJC Scopus subject areas

- Electronic, Optical and Magnetic Materials
- Atomic and Molecular Physics, and Optics
- Safety, Risk, Reliability and Quality
- Condensed Matter Physics
- Surfaces, Coatings and Films
- Electrical and Electronic Engineering