Efficient algorithms for computing the reliability of permutation and interval graphs

DOI10.1002/NET.3230200706MaRDI QIDQ3211090zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

chordal graphscographsinterval graphsperfect edgespermutation graphsreliability of networksreliable Steiner treeunreliable nodes

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Incidence matrices and interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(10)

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

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)