The Complexity of Reliability Computations in Planar and Acyclic Graphs.
- 1 December 1984
- report
- Published by Defense Technical Information Center (DTIC)
Abstract
The author shows 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. Keywords include: Reliability; complexity; planar graph; acyclic graph; NP-hard; P-complete.Keywords
This publication has 0 references indexed in Scilit: