Efficient algorithms for computing the reliability of permutation and interval graphs

DOI10.1002/NET.3230200706zbMATH Open0722.90028OpenAlexW2063549430MaRDI QIDQ3211090FDOQ3211090

Authors: Hosam M. AboElFotoh, Charles J. Colbourn 

Publication date: 1990

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230200706

Recommendations

• A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
• Computing residual connectedness reliability for restricted networks
• An O(n*log(n)) algorithm to compute the all-terminal reliability of (K/sub 5/, K/sub 2.2.2/) free networks
• A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability
• Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula

zbMATH Keywords

interval graphschordal graphscographspermutation graphsunreliable nodesperfect edgesreliability of networksreliable Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Reliability, availability, maintenance, inspection in operations research (90B25) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs

Cited In (10)

• Network reliability and the probabilistic estimation of damage from fire spread
• Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs
• Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• A note on bounding \(k\)-terminal reliability
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• Computing residual connectedness reliability for restricted networks
• Network reliability: Heading out on the highway
• Reliabilities of Consecutive-2 Graphs
• Computing the \(K\)-terminal reliability of directed path graphs

This page was built for publication: Efficient algorithms for computing the reliability of permutation and interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3211090)