×

zbMATH — the first resource for mathematics

The complexity of reliability computations in planar and acyclic graphs. (English) Zbl 0606.68066
We show that the problem of computing source-sink reliability is NP-hard, in fact #P-complete, even for undirected and acyclic directed source- sink planar graphs having vertex degree at most three. Thus the source- sink reliability problem is unlikely to have an efficient algorithm, even when the graph can be laid out on a rectilinear grid.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI