The Complexity of Reliability Computations in Planar and Acyclic Graphs | Zendy

J. Scott Provan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Complexity of Reliability Computations in Planar and Acyclic Graphs

Author(s) -

J. Scott Provan

Publication year - 1986

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0215050

Subject(s) - directed acyclic graph , directed graph , planar graph , computer science , vertex (graph theory) , computation , combinatorics , grid , np complete , feedback vertex set , computational complexity theory , discrete mathematics , mathematics , algorithm , graph , geometry

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research