Efficient algorithms for computing the reliability of permutation and interval graphs

DOI10.1002/net.3230200706zbMath0722.90028OpenAlexW2063549430MaRDI QIDQ3211090

Hosam M. F. 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 graphspermutation graphsunreliable nodesperfect edgesreliability of networksreliable Steiner tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Communication networks in operations research (90B18) 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)

Related Items (7)

A parallel algorithm for computing Steiner trees in strongly chordal graphs ⋮ Network reliability and the probabilistic estimation of damage from fire spread ⋮ Network reliability: Heading out on the highway ⋮ Computing \(K\)-terminal reliability of \(d\)-trapezoid graphs ⋮ A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs ⋮ Computing residual connectedness reliability for restricted networks ⋮ Computing the \(K\)-terminal reliability of directed path graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs

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