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

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)

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)

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